题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=20332
【思路】
时光倒流+名次树（rank tree）。
所谓“时光倒流”即逆向处理，因为D删除边并不好操作所以我们倒着处理，删除边转化为添加边，C转化为将weight变回操作前的数，Q不变。
名次树实现以上操作：名次树是Treap+s域实现的，可以提供kth即查询第k大的数的操作和Treap的所有功能。
1）对于D(x)：合并from[x]与to[x]所在的rank tree，后序思想，将src中的结点逐个添加到dest中，采用启发式合并。
2）对于Q(x,k)：调用kth操作同时累计cnt与tot。
3)对于C(x,v)：调用一次romove(root[findset(x)],weight[x])，再调用一次insert(root[findset(x)],v)。
用到一个并查集快速寻找x所属rank tree的根。
【代码】
#include<cstdio>
#include<ctime>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<iostream>
#define FOR(a,b,c) for(int a=(b);a<=(c);a++)
using namespace std; const int maxn = +;
//Treap相关
struct Node{
Node *ch[];
int r,v,s; //r为优先级 v为键值 s为结点总数
Node(int w) :v(w) { ch[]=ch[]=NULL; s=; r=rand(); }
int cmp(int x) const{ //x应在左子树d=0 x应在右子树d=1
if(x==v) return -;
return x<v? :;
}
int cmp2(int x) const{ return x<v? :; }
void maintain() { //名次树维护 s
s=;
if(ch[]!=NULL) s+=ch[]->s;
if(ch[]!=NULL) s+=ch[]->s;
}
};
void rotate(Node* &o,int d) { //旋转操作 d=0左旋d=1右旋
Node* k=o->ch[d^]; o->ch[d^]=k->ch[d]; k->ch[d]=o;
o->maintain();k->maintain(); o=k;
}
void insert(Node* &o,int x) {
if(o==NULL) o=new Node(x);
else {
int d=o->cmp2(x); //可能会有键值相等的结点
insert(o->ch[d],x);
if(o->ch[d]->r > o->r) rotate(o,d^); //如果插入之后不满足堆的性质则反方向旋转
}
o->maintain(); //维护
}
void remove(Node* &o,int x) {
int d=o->cmp(x);
if(d==-) {
Node *u=o;
if(o->ch[]!=NULL && o->ch[]!=NULL){ //根据左右子[优先级]旋转 旋转后递归删除x
int d2=o->ch[]->r > o->ch[]->r? :;
rotate(o,d2); remove(o->ch[d2],x);
}
else {
if(o->ch[]!=NULL) o=o->ch[]; else o=o->ch[];
delete u;
}
}
else
remove(o->ch[d],x);
if(o!=NULL) o->maintain();
}
//名次树相关
int kth(Node* o,int k) { //返回第k[大]的数
if(o==NULL || k<= || k>o->s) return ;
int s=o->ch[]==NULL? :o->ch[]->s;
if(k==s+) return o->v;
else if(k<=s) return kth(o->ch[],k);
else return kth(o->ch[],k-s-);
}
void mergeto(Node* &src,Node* &dest) { //[后序遍历]合并两棵名次树
if(src->ch[]!=NULL) mergeto(src->ch[],dest);
if(src->ch[]!=NULL) mergeto(src->ch[],dest);
insert(dest,src->v);
delete src;
src=NULL;
}
void removetree(Node* &o) { //[后序遍历]删除一棵名次树
if(o->ch[]!=NULL) removetree(o->ch[]);
if(o->ch[]!=NULL) removetree(o->ch[]);
delete o;
o=NULL;
}
//并查集相关
int pa[maxn];
int findset(int u) { return u==pa[u]? u:pa[u]=findset(pa[u]); }
//题目相关
Node* root[maxn];
int weight[maxn],from[maxn],to[maxn];
bool removed[maxn];
int n,m,cnt,kase;
long long sum;
struct Command{ char type; int a,b;
};
vector<Command> cs; void addedge(int i) {
int u=findset(from[i]),v=findset(to[i]);
if(u!=v) {
if(root[u]->s > root[v]->s) { pa[v]=u; mergeto(root[v],root[u]); }
else { pa[u]=v; mergeto(root[u],root[v]); }
}
}
void query(int x,int k) {
cnt++;
sum+=kth(root[findset(x)],k);
}
void changeWeight(int x,int p) {
int u=findset(x);
remove(root[u],weight[x]);
insert(root[u],p);
weight[x]=p;
} int main() {
srand(time()); //初始化随机数种子
kase=;
while(scanf("%d%d",&n,&m)== && (n&&m)) {
FOR(i,,n) scanf("%d",&weight[i]);
FOR(i,,m) scanf("%d%d",&from[i],&to[i]);
char type;
memset(removed,,sizeof(removed));
cs.clear();
while(scanf(" %c",&type)== && type!='E') {
int x=,p=;
scanf("%d",&x);
if(type=='D') removed[x]=;
if(type=='Q') scanf("%d",&p);
if(type=='C') {
scanf("%d",&p);
swap(p,weight[x]);
}
cs.push_back((Command){type,x,p});
}
FOR(i,,n) {
pa[i]=i; if(root[i]!=NULL) removetree(root[i]);
root[i]=new Node(weight[i]);
}
FOR(i,,m) if(!removed[i]) addedge(i);
int d=cs.size(); sum=cnt=;
for(int i=d-;i>=;i--) {
if(cs[i].type=='D') addedge(cs[i].a);
if(cs[i].type=='Q') query(cs[i].a,cs[i].b);
if(cs[i].type=='C') changeWeight(cs[i].a,cs[i].b);
}
printf("Case %d: %.6lf\n",++kase,sum/(double)cnt);
}
return ;
}