题意：
给一个无向图，再给一系列操作（以下3种），输出最后的平均查询结果。
（1）D X 删除第x条边。
（2）Q X k 查询与点X相连的连通分量中第k大的点的权值。
（3）C X v 将点X的权值改为v。
思路：
第一点，由于需要删除边，不是很方便，所以可以先将所有操作存起来，反序来操作，这样删边就变成加边，方便了不少。每次加边时若两点不属于同个连通分量，就将点少的整个连通分量中的点逐个插入到另一个连通分量中。
第二点，查第k大，这个比较简单，只需要维护Treap上每个点的的左右孩子数量就可以了。查的只是某个点所属连通分量中的第k大值，与真实图是怎样的无关。
第三点，改权值，这个麻烦。可以先删除该点，再插入改过权的该点。删除方式就是将该点旋转到成为叶子，然后删除它就方便了，因为还需要维护堆的性质，所以往下旋转比较方便的。
坑点：随时要注意更新每个连通分量的根节点，也就是说必须用引用的时候，尽量用引用。在第一点操作时，需要插很多点，每插1个点都可能成为根，所以要随时更新根节点。
#include <bits/stdc++.h>
#define pii pair<int,int>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int N=;
bool single[N];
int w[N], from[N*], to[N*], cut[N*], pre[N], root[N];
struct opera
{
char type;
int a, b;
opera(char t,int a,int b):type(t),a(a),b(b){};
};
deque<opera> que;
struct node //Treap
{
int val, pre, rank; //ran是优先级
int ch[], son[];
node(){};
node(int val):val(val)
{
rank=rand();
ch[]=ch[]=son[]=son[]=pre=;
};
}nod[N]; int find(int x){return pre[x]==x? x: pre[x]=find(pre[x]);} int Query(int t,int k) //找第k大
{
if( k< || nod[t].son[] + nod[t].son[] + < k) return ; //k太小or太大
if( nod[t].son[]==k- ) return nod[t].val;
if( nod[t].son[]>k- ) return Query(nod[t].ch[], k);
else return Query(nod[t].ch[], k-nod[t].son[]-);
} void Rotate(int t, int d) //d为方向,0是左旋，1是右
{
int far=nod[t].pre;
int son=nod[t].ch[d]; //far的孩子
int gra=nod[far].pre; //far的父亲 nod[son].pre=far;
nod[t].pre=gra;
nod[far].pre=t; nod[far].ch[d^]=son;
nod[t].ch[d]=far;
nod[gra].ch[nod[gra].ch[]==far]=t; //子树中的节点要更新
nod[far].son[d^]=nod[t].son[d];
nod[t].son[d]+=+nod[far].son[d]; //别忘了还有far也是个节点 if(gra==) root[find(far)]=t; //更新连通分量的根节点
} int get_child(int t) //返回孩子编号，总是返回rank较大的那个。0表示无孩子
{
if(!nod[t].ch[] && !nod[t].ch[]) return ;
if(nod[t].ch[] && nod[t].ch[])
{
int L=nod[t].ch[], R=nod[t].ch[];
if(nod[L].rank < nod[R].rank) return R;
else return L;
}
if(nod[t].ch[]) return nod[t].ch[];
else return nod[t].ch[];
} void Insert(int root,int t) //将t插入到root中
{
if(nod[t].val<nod[root].val)
{
nod[root].son[]++;
if(nod[root].ch[]) Insert(nod[root].ch[], t);
else nod[root].ch[]=t, nod[t].pre=root;
}
else
{
nod[root].son[]++;
if(nod[root].ch[]) Insert(nod[root].ch[], t);
else nod[root].ch[]=t, nod[t].pre=root;
}
int son=nod[root].ch[];
if( nod[son].rank > nod[root].rank ) Rotate(son, ); //孩子的rank比我还大
}
void clear(int t,int v) //清空点t，值改为v
{
nod[t].pre=nod[t].ch[]=nod[t].ch[]=nod[t].son[]=nod[t].son[]=;
nod[t].val=v;
} void Merge(int &root, int t) //递归将t中的节点逐个拆出
{
if(nod[t].ch[]>) Merge(root, nod[t].ch[]);
if(nod[t].ch[]>) Merge(root, nod[t].ch[]);
clear(t, nod[t].val); //值仍不变
single[root]=; //非单身了
single[t]=;
Insert(root, t); //将t插入到root中
} void add_edge(int i)
{
int u=find(from[i]), v=find(to[i]); //两点所在连通分量
if(u!=v) //这里也会去掉重边
{
int &uu=root[u], &vv=root[v]; //找到连通分量的树根。注意：必须是引用，有可能每插一次就换根了。
if( nod[uu].son[]+nod[uu].son[] < nod[vv].son[]+nod[vv].son[]) //uu小
pre[u]=v, Merge(vv, uu); //uu拆出来装到vv上面去
else
pre[v]=u, Merge(uu, vv);
}
} void change(int t,int v) //将t的权值改为v
{
if(single[t]==true){nod[t].val=v;return ;} //仅有1个点,直接改
int far, son, tmp;
while( (son=get_child(t))!= ) Rotate( son, nod[t].ch[]==son); //先把t转到底端
tmp=t;
while( nod[tmp].pre!= ) //调整到根节点的孩子数量,沿途减1。
{
far=nod[tmp].pre;
nod[far].son[nod[far].ch[]==tmp]--;
tmp=far;
}
far=nod[t].pre;
nod[far].ch[ nod[far].ch[]==t ]=; //需要做的只是改变父亲的孩子指针。
clear(t, v);
Insert(root[find(t)], t); //改完值插到root中。
} double cal(int n,int m)
{
for(int i=; i<=n; i++) pre[i]=root[i]=i,nod[i]=node(w[i]); //初始时，root和连通分量编号都是自己
for(int i=; i<=m; i++) if(cut[i]==) add_edge(i);
LL ans=, cnt=;
while(!que.empty())
{
opera p=que.front();que.pop_front();
if(p.type=='D') add_edge(p.a); //加边
if(p.type=='Q') cnt++,ans+=Query(root[find(p.a)], p.b);
if(p.type=='C') change(p.a, p.b); //改权值
}
return ans/(double)cnt;
} int main()
{
freopen("input.txt", "r", stdin);
int a, b, c, n, m, Case=;
char op;
while(cin>>n>>m, n+m)
{
memset(single, , sizeof(single));
memset(cut, , sizeof(cut));
for(int i=; i<=n; i++) scanf("%d", &w[i]);
for(int i=; i<=m; i++) scanf("%d %d", &from[i], &to[i]); while(cin>>op,op!='E')
{
if(op=='D'){scanf("%d",&a);cut[a]=;} //删边
if(op=='Q') scanf("%d%d",&a,&b); //查询
if(op=='C'){scanf("%d%d",&a,&b),swap(w[a], b);} //改权
que.push_front(opera(op, a, b));
}
printf("Case %d: %.6f\n", ++Case, cal(n, m));
}
return ;
}
AC代码