删除边的操作不容易实现，那么就先离线然后逆序来做。
逆序就变成了合并，用并存集判断连通，用Treap树来维护一个连通分量里的名次。
Treap = Tree + Heap。用一个随机的优先级来平衡搜索树。
名次查询需要维护树的结点数量，假设当前在u点，u的左子树有n个结点，那么u的就是以u为根的树上第n+1小的。
如果查询的不是n+1，那么根据结点数量判断一下在哪颗子树上，然后去查询。
树的合并就将结点数少的树上的点往结点数多的树里面插，然后删掉结点少的树。
修改权值就分解成删除点和插点。
写的时候要分清哪些指针本身是要修改的，要用引用。哪些指针可能是NULL，不应该访问。
试过将null设定为常指针，快了25ms，用内存池模拟new 分配内存，快了50ms，但是结点数要开到maxn的两倍，（在这RE了很多次）。
如果new 的效率足够的话还是不要用内存池了，搞不好就RE了。
这题刷新了挂题发数，不过总算是会写Treap了。
#include<bits/stdc++.h> using namespace std; struct Node { Node *ch[2]; int v,r,s; void maintain() { s = 1+ch[0]->s+ch[1]->s; } }; Node *const null = new Node(); inline Node *newNode(int x) { Node* t = new Node(); t->ch[0]=t->ch[1] = null; t->s = 1; t->r = rand(); t->v = x; return t; } void rot(Node*&o,int d) { Node*t = o->ch[d^1]; o->ch[d^1] = t->ch[d]; t->ch[d] = o; o->maintain(); t->maintain(); o = t; } void inst(Node*&o,int x) { if(o==null){ o = newNode(x); }else { int d = x > o->v ? 1:0; inst(o->ch[d],x); if(o->ch[d]->r > o->r) rot(o,d^1); } o->maintain(); } inline int tcmp(int a,int b) { if(a == b) return -1; return a > b? 0 : 1; } void rmov(Node*&o,int x) { //if(o == null) return; int d = tcmp(o->v,x); if(~d){ rmov(o->ch[d],x); }else { Node*lc = o->ch[0],*rc = o->ch[1]; if(lc!=null &&rc != null){ int d2 = lc->r > rc->r? 1:0; rot(o,d2); rmov(o->ch[d2],x); }else { Node *t = o; if(lc == null) o = rc; else o = lc; delete t; } } if(o != null) o->maintain(); } const int maxc = 5e5+5, maxn = 2e4+5, maxm = 6e4+5; struct Cmd { char tp; int x,p; }cmd[maxc]; int n,m,wei[maxn],fro[maxm],to[maxm],rmvd[maxm]; int pa[maxn]; int fdst(int x){ return x==pa[x]?x:pa[x]=fdst(pa[x]); } Node *rt[maxn]; //k>0 int kth(Node*o,int k) { if(o == null || k <= 0 || k > o->s) return 0; // int s = o->ch[1]->s; if(k == s+1) return o->v; if(k <= s) return kth(o->ch[1],k); return kth(o->ch[0],k-s-1); } void mgto(Node*&u,Node*&v) { if(u->ch[0] != null) mgto(u->ch[0],v); if(u->ch[1] != null) mgto(u->ch[1],v); inst(v,u->v); delete u; u = null; } void rmvTree(Node*&o) { if(o->ch[1] != null) rmvTree(o->ch[1]); if(o->ch[0] != null) rmvTree(o->ch[0]); delete o; o = null; } inline void addEdge(int i) { int u = fdst(fro[i]), v = fdst(to[i]); if(u != v){ if(rt[u]->s < rt[v]->s){ pa[u] = v; mgto(rt[u],rt[v]); }else { pa[v] = u; mgto(rt[v],rt[u]); } } } int qct; long long qtot; inline void qry(int x,int p) { if(p>0){ qtot+=kth(rt[fdst(x)],p); } qct++; } inline void chgw(int x,int p) { int u = fdst(x); rmov(rt[u],wei[x]); inst(rt[u],wei[x]=p); } int main() { //freopen("in.txt","r",stdin); int kas = 0; null->s = 0; null->ch[0] = null->ch[1] = null; fill(rt,rt+maxn,null); while(~scanf("%d%d",&n,&m)&&n){ for(int i = 1; i <= n; i++) scanf("%d",wei+i); for(int i = 1; i <= m; i++) scanf("%d%d",fro+i,to+i); kas++; int c = 0; while(true){ char tp; int x,p; scanf(" %c",&tp); if(tp == 'E') break; scanf("%d",&x); if(tp == 'D') rmvd[x] = kas; else if(tp == 'Q') scanf("%d",&p); else if(tp == 'C') { p = wei[x]; scanf("%d",wei+x); } cmd[c++] = {tp,x,p}; } for(int i = 1; i <= n; i++){ pa[i] = i; if(rt[i] != null) rmvTree(rt[i]); rt[i] = newNode(wei[i]); } for(int i = 1; i <= m; i++) if(rmvd[i] != kas) addEdge(i); qtot = qct = 0; while(c--){ Cmd &cq = cmd[c]; if(cq.tp == 'Q') qry(cq.x,cq.p); else if(cq.tp == 'C') chgw(cq.x,cq.p); else if(cq.tp == 'D')addEdge(cq.x); } printf("Case %d: %.6lf ",kas,qtot/(double)qct); } return 0; }