Description
给出一个(n(nleq2 imes10^4))个点，(m(mleq6 imes10^4))条边的有点权无向图。进行若干次操作：
- 删除第(i)条边。
- 求与点(u)连通的所有点中，权值第(k)大的点的权值。
- 将点(u)的权值改为(x)。
Solution
将操作离线，并从终止状态开始反向操作：删边变为加边，将权值由(x)修改成(y)变为由(y)改为(x)。
用splay维护每一个连通块内的权值，加边时启发式合并两棵splay，修改时删除再加入。
启发式合并：合并两个数据结构时，将小的中的每个节点加入大的中。因为合成的数据结构大小至少是小的的两倍，所以一个节点最多被合并(O(logn))次，总复杂度就是(O(nlogn))。
Code
//Graph and Queries
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int const N=2e4+10;
int n,m;
struct edge{int u,v,able;} ed[N*3];
int cntQ;
struct _query{char opt; int x,y;} qu[N*23];
int pre[N];
int find(int x) {return pre[x]==x?x:pre[x]=find(pre[x]);}
int fa[N],ch[N][2],val[N],siz[N];
int wh(int p) {return p==ch[fa[p]][1];}
void reset(int p) {fa[p]=ch[p][0]=ch[p][1]=0; siz[p]=1;}
void update(int p) {siz[p]=siz[ch[p][0]]+1+siz[ch[p][1]];}
void rotate(int p)
{
int q=fa[p],r=fa[q],w=wh(p);
fa[p]=r; if(r) ch[r][wh(q)]=p;
fa[ch[q][w]=ch[p][w^1]]=q;
fa[ch[p][w^1]=q]=p;
update(q),update(p);
}
void splay(int p) {for(int q;q=fa[p];rotate(p)) if(fa[q]) rotate(wh(p)^wh(q)?p:q);}
int root(int p) {while(fa[p]) p=fa[p]; return p;}
void ins(int rt,int x)
{
if(rt==x) return;
int p=rt,q=0; reset(x);
while(p) q=p,p=ch[q][val[q]<val[x]];
fa[ch[q][val[q]<val[x]]=x]=q; splay(x);
}
int del(int p)
{
splay(p); int chCnt=(ch[p][0]>0)+(ch[p][1]>0);
if(chCnt==1)
{
int q=ch[p][ch[p][1]>0];
fa[q]=0; reset(p); return q;
}
int q=ch[p][0]; while(ch[q][1]) q=ch[q][1];
splay(q); fa[ch[q][1]=ch[p][1]]=q,update(q);
return q;
}
int rnk(int rt,int x)
{
x=siz[rt]-x+1;
int p=rt;
while(p)
if(x<=siz[ch[p][0]]) p=ch[p][0];
else if(siz[ch[p][0]]+1==x) return val[p];
else if(x>siz[ch[p][0]]+1) x-=siz[ch[p][0]]+1,p=ch[p][1];
return 0;
}
int cntT,tmp[N];
void list(int p)
{
if(p==0) return;
list(ch[p][0]),tmp[++cntT]=p,list(ch[p][1]);
}
void merge(int rt1,int rt2)
{
if(rt1==rt2) return;
if(siz[rt1]>siz[rt2]) swap(rt1,rt2);
cntT=0,memset(tmp,0,sizeof tmp); list(rt1);
for(int i=1;i<=cntT;i++) ins(root(rt2),tmp[i]);
}
void change(int p,int x)
{
int rt=root(p); if(siz[rt]==1) {val[p]=x; return;}
int q=del(p); val[p]=x,ins(root(q),p);
}
void init()
{
n=m=0; memset(ed,0,sizeof ed);
cntQ=0; memset(qu,0,sizeof qu);
memset(fa,0,sizeof fa),memset(ch,0,sizeof ch);
memset(val,0,sizeof val),memset(siz,0,sizeof siz);
}
int main()
{
for(int owo=1;true;owo++)
{
init();
scanf("%d%d",&n,&m); if(n==0&&m==0) break;
for(int i=1;i<=n;i++) scanf("%d",&val[i]),siz[i]=1;
for(int i=1;i<=m;i++) scanf("%d%d",&ed[i].u,&ed[i].v),ed[i].able=true;
for(int i=1;true;i++)
{
scanf("
%c",&qu[i].opt);
if(qu[i].opt=='E') break;
scanf("%d",&qu[i].x);
if(qu[i].opt=='D') ed[qu[i].x].able=false;
else if(qu[i].opt=='Q') scanf("%d",&qu[i].y);
else if(qu[i].opt=='C') qu[i].y=val[qu[i].x],scanf("%d",&val[qu[i].x]);
cntQ=i;
}
for(int i=1;i<=n;i++) pre[i]=i;
for(int i=1;i<=m;i++)
{
if(!ed[i].able) continue;
int u=ed[i].u,v=ed[i].v;
if(find(u)!=find(v)) pre[find(u)]=find(v);
}
for(int i=1;i<=n;i++) if(i!=find(i)) ins(root(find(i)),i);
long long ans=0; int cnt0=0;
for(int i=cntQ;i>=1;i--)
{
char opt=qu[i].opt; int x=qu[i].x,y=qu[i].y;
if(opt=='D') merge(root(ed[x].u),root(ed[x].v));
else if(opt=='Q') ans+=rnk(root(x),y),cnt0++;
else if(opt=='C') change(x,y);
}
printf("Case %d: %.6lf
",owo,(double)ans/cnt0);
}
return 0;
}
P.S.
原来启发式合并这么简单...我以前以为超级高大上的
为什么HDU净是多组测试数据，还不告诉你有多少操作叫你自己读...