反向操作，先求出最终状态，再反向操作。
然后就是Treap 的合并，求第K大值。
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<stack>
#include<cmath>
#include<utility>
using namespace std;
typedef long long LL;
struct Treap{
int size,key,pri;
Treap *ch[2];
Treap(int key){
size=1;
pri=rand();
this->key=key;
ch[0]=ch[1]=NULL;
}
int compare(int x) const{
if(x==key) return -1;
return x<key? 0:1;
}
void Maintain(){
size=1;
if(ch[0]!=NULL){
size+=ch[0]->size;
}
if(ch[1]!=NULL){
size+=ch[1]->size;
}
}
};
void Rotate(Treap* &t,int d){
Treap *k=t->ch[d^1];
t->ch[d^1]=k->ch[d];
k->ch[d]=t;
t->Maintain();
k->Maintain();
t=k;
}
void Insert(Treap* &t,int x){
if(t==NULL){
t=new Treap(x);
}else{
int d=x < t->key ? 0:1;
Insert(t->ch[d],x);
if(t->ch[d]->pri > t->pri){
Rotate(t,d^1);
}
}
t->Maintain();
}
void Delete(Treap* &t,int x){
int d=t->compare(x);
if(d==-1){
Treap *tmp=t;
if(t->ch[0]==NULL){
t=t->ch[1];
delete tmp;
tmp=NULL;
}else if(t->ch[1]==NULL){
t=t->ch[0];
delete tmp;
tmp=NULL;
}else{
int k=t->ch[0]->pri > t->ch[1]->pri ? 1:0;
Rotate(t,k);
Delete(t->ch[k],x);
}
}else{
Delete(t->ch[d],x);
}
if(t!=NULL){
t->Maintain();
}
}
int Kth(Treap *t,int k){
if(t==NULL||k<=0||k>t->size){
return 0;
}
if(t->ch[0]==NULL&&k==1){
return t->key;
}
if(t->ch[0]==NULL){
return Kth(t->ch[1],k-1);
}
if(t->ch[0]->size>=k){
return Kth(t->ch[0],k);
}
if(t->ch[0]->size+1==k){
return t->key;
}
return Kth(t->ch[1],k-1-t->ch[0]->size);
}
void DeleteTreap(Treap* &t){//删除，释放内存
if(t==NULL) return;
if(t->ch[0]!=NULL){
DeleteTreap(t->ch[0]);
}
if(t->ch[1]!=NULL){
DeleteTreap(t->ch[1]);
}
delete t;
t=NULL;
}
int n, m;
int g[100000][3];
stack<int> val[40000];
struct Ope{
char t;
int a, b;
void init(char t1, int a1 = 0, int b1 = 0){
t = t1;
a = a1;
b = b1;
}
}op[1000000];
int fa[40000];
Treap* fax[40000];
void mergeTreap(Treap* &a, Treap* &b){
if(a){
if(a -> ch[0]){
mergeTreap(a -> ch[0], b);
}
if(a -> ch[1]){
mergeTreap(a -> ch[1], b);
}
Insert(b, a -> key);
delete a;
a = NULL;
}
}
int uFind(int x){
return (fa[x] == x) ? x : fa[x] = uFind(fa[x]);
}
void add(int u, int v){
int fx = uFind(u);
int fy = uFind(v);
if(fx != fy){
if(fax[fx] -> size < fax[fy] -> size){
mergeTreap(fax[fx], fax[fy]);
fa[fx] = fy;
}else{
mergeTreap(fax[fy], fax[fx]);
fa[fy] = fx;
}
}
}
int main(){
int cas = 0;
while(~scanf("%d %d", &n, &m) && n || m){
for(int i = 1; i <= n; i++){
fa[i] = i;
fax[i] = NULL;
int tp;
scanf("%d", &tp);
tp = -tp;
while(!val[i].empty()){
val[i].pop();
}
val[i].push(tp);
}
for(int i = 0; i < m; i++){
int u, v;
scanf("%d %d", &u, &v);
g[i][0] = u;
g[i][1] = v;
g[i][2] = 0;
}
char str[10];
int tot = 0;
while(~scanf("%s", str) && str[0] != 'E'){
int a, b;
if(str[0] == 'D'){
scanf("%d", &a);
a--;
g[a][2] = 1;
}else if(str[0] == 'C'){
scanf("%d %d", &a, &b);
b = -b;
val[a].push(b);
}else{
scanf("%d %d", &a, &b);
}
op[tot++].init(str[0], a, b);
}
for(int i = 1; i <= n; i++){
Insert(fax[i], val[i].top());
}
for(int i = 0; i < m; i++){
if(g[i][2] == 0){
add(g[i][0], g[i][1]);
}
}
int cnt = 0;
LL ans = 0;
while(tot--){
if(op[tot].t == 'C'){
int rt = uFind(op[tot].a);
Delete(fax[rt], val[op[tot].a].top());
val[op[tot].a].pop();
Insert(fax[rt], val[op[tot].a].top());
}else if(op[tot].t == 'D'){
int id = op[tot].a;
add(g[id][0], g[id][1]);
}else{
cnt++;
ans += Kth(fax[ uFind(op[tot].a) ], op[tot].b);
}
}
printf("Case %d: %.6f
", ++cas, (double)-ans / cnt);
for(int i = 1; i <= n; i++){
int fx = uFind(i);
if(fax[fx] != NULL){
DeleteTreap(fax[fx]);
}
}
}
return 0;
}
已经释放了内存，但在VS中使用_CrtDumpMemoryLeaks()函数检查还是有内存泄漏问题，原因还没弄清楚