题意：一个N个点（编号从1开始），M条边的无向图（编号从1开始），有3种操作：
D X：把编号为X的边删了；
Q X K：查询编号为X的结点所在连通分量第K大的元素；
C X V：将编号为X的结点的权值修改为V。
问所有查询的结果的平均值（1 <= N <= 20000, 0 <= M <= 60000, -10^6 <= 点权 <= 10^6, 1 <= Q操作次数 <= 2 * 10^5, C操作次数 <= 2 * 10^5）。
题目链接：
——>>LJ《训练指南》Treap树的例题，题目中关于Q操作的话：among all vertexes currently connected with vertex X，总觉得指的是与X直接相连的结点，可实现上却应理解为X所在连通分量的所有结点。
#include#include #include using namespace std;const int maxn = 20000 + 10;const int maxm = 60000 + 10;const int maxc = 500000 + 10;struct Command{ char type; int x, p; Command(char type = '\0', int x = 0, int p = 0):type(type), x(x), p(p){}};struct Node{ Node *ch[2]; int r; int v; int s; Node(int v):v(v){ ch[0] = ch[1] = NULL; r = rand(); s = 1; } bool operator < (const Node& e) const{ return r < e.r; } int cmp(int x) const{ if(x == v) return -1; return x < v ? 0 : 1; } void maintain(){ s = 1; if(ch[0] != NULL) s += ch[0]->s; if(ch[1] != NULL) s += ch[1]->s; }};int N, M, weight[maxn], from[maxm], to[maxm], fa[maxn], kase, c, query_cnt;long long query_tot;bool removed[maxm];Command commands[maxc];Node *root[maxn];int Find(int x){ return x == fa[x] ? x : Find(fa[x]);}void removetree(Node* &x){ if(x->ch[0] != NULL) removetree(x->ch[0]); if(x->ch[1] != NULL) removetree(x->ch[1]); delete x; x = NULL;}void rotate(Node* &o, int d){ Node* k = o->ch[d^1]; o->ch[d^1] = 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 = x < o->v ? 0 : 1; insert(o->ch[d], x); if(o->ch[d] > o) rotate(o, d^1); } o->maintain();}void remove(Node* &o, int x){ int d = o->cmp(x); if(d == -1){ Node* u = o; if(o->ch[0] != NULL && o->ch[1] != NULL){ int d2 = o->ch[0] > o->ch[1] ? 1 : 0; rotate(o, d2); remove(o->ch[d2], x); } else{ if(o->ch[0] == NULL) o = o->ch[1]; else o = o->ch[0]; delete u; } } else remove(o->ch[d], x); if(o != NULL) o->maintain();}void mergeto(Node* &src, Node* &dest){ if(src->ch[0] != NULL) mergeto(src->ch[0], dest); if(src->ch[1] != NULL) mergeto(src->ch[1], dest); insert(dest, src->v); delete src; src = NULL;}void addEdge(int x){ int u = Find(from[x]); int v = Find(to[x]); if(u != v){ if(root[u]->s < root[v]->s){ fa[u] = v; mergeto(root[u], root[v]); } else{ fa[v] = u; mergeto(root[v], root[u]); } }}int kth(Node* o, int k){ if(o == NULL || k <= 0 || k > o->s) return 0; int s = (o->ch[1] == NULL ? 0 : o->ch[1]->s); if(k == s+1) return o->v; else if(k < s+1) return kth(o->ch[1], k); else return kth(o->ch[0], k-s-1);}void query(int x, int k){ query_cnt++; query_tot += kth(root[Find(x)], k);}void change_weight(int x, int v){ int u = Find(x); remove(root[u], weight[x]); insert(root[u], v); weight[x] = v;}void read(){ for(int i = 1; i <= N; i++) scanf("%d", &weight[i]); for(int i = 1; i <= M; i++) scanf("%d%d", &from[i], &to[i]); c = 0; memset(removed, 0, sizeof(removed)); while(1){ char type; int X, K, V; scanf(" %c", &type); if(type == 'E') break; scanf("%d", &X); if(type == 'D') removed[X] = 1; else if(type == 'Q') scanf("%d", &K); else{ scanf("%d", &V); K = weight[X]; weight[X] = V; } commands[c++] = Command(type, X, K); }}void build(){ for(int i = 1; i <= N; i++){ fa[i] = i; if(root[i] != NULL) removetree(root[i]); root[i] = new Node(weight[i]); } for(int i = 1; i <= M; i++) if(!removed[i]) addEdge(i);}void solve(){ query_tot = query_cnt = 0; for(int i = c-1; i >= 0; i--){ if(commands[i].type == 'D') addEdge(commands[i].x); else if(commands[i].type == 'Q') query(commands[i].x, commands[i].p); else change_weight(commands[i].x, commands[i].p); } printf("Case %d: %.6lf\n", kase++, (double)query_tot / query_cnt);}int main(){ kase = 1; while(scanf("%d%d", &N, &M) == 2){ if(!N && !M) return 0; read(); build(); solve(); } return 0;}