题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3726
题意：n个点m条边的一张无向图，每个点有一个权值， 有3中操作。
D X 删除第X条边
Q X K 计算与X点相连所有点中第k大的权值
C X V把X的权值改为 V
输出 Q次询问的平均值
大白上的例题， 离线处理，把所有操作 反过来处理，，这样删边变成了 加边，，瞬间好处理多了。。细节也有很多。
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-;
const int maxn = 2e4+;
int n, m, val[maxn];
int pa[maxn];
void init()
{
for (int i = ; i <= n; i++)
{
pa[i] = i;
}
}
int find(int x)
{
return pa[x] = (pa[x] == x ? x : find(pa[x]));
}
struct Node
{
Node* ch[];
int key, r, siz;
Node (int x)
{
key = x;
siz = ;
ch[] = ch[] = NULL;
r = rand();
}
bool operator < (const Node &rhs)const
{
return r < rhs.r;
}
int cmp(int x)
{
if (x == key)
return -;
return x < key ? : ;
}
void maintain()
{
siz = ;
if (ch[] != NULL)
siz += ch[] -> siz;
if (ch[] != NULL)
siz += ch[] -> siz;
}
};
void rotate(Node* &root, int d)
{
Node* tmp = root -> ch[d^];
root -> ch[d^] = tmp -> ch[d];
tmp -> ch[d] = root;
root -> maintain();
tmp -> maintain();
root = tmp;
}
void insert(Node* &root, int x)
{
if (root == NULL)
root = new Node (x);
else
{
int d = x < root -> key ? : ;
insert (root ->ch[d], x);
if (root -> ch[d] -> r > root -> r)
rotate(root, d^); }
root -> maintain();
}
void dele(Node* &root, int x)
{
int d = root -> cmp(x);
if (d == -)
{
Node* tmp = root;
if (root -> ch[] != NULL && root -> ch[] != NULL)
{
int d1 = (root -> ch[] -> r > root -> ch[] -> r ? : );
rotate(root, d1^);
dele(root -> ch[d1^], x);
}
else
{
if (root -> ch[] == NULL)
root = root -> ch[];
else
root = root -> ch[];
delete tmp;
}
}
else
dele(root->ch[d], x);
if (root != NULL)
root -> maintain();
}
int Get_kth(Node* root, int k)
{
if (root == NULL || k <= || root -> siz < k)
return ;
int s = root -> ch[] == NULL ? : root -> ch[] -> siz;
if (s + == k)
return root -> key;
if (s + > k)
return Get_kth(root -> ch[], k);
else
return Get_kth(root -> ch[], k-s-); }
Node* root[maxn];
void merge_tree(Node* &src, Node* &fa)
{
if (src -> ch[] != NULL)
merge_tree(src -> ch[], fa);
if (src -> ch[] != NULL)
merge_tree(src -> ch[], fa);
insert(fa, src -> key);
delete src;
src = NULL;
}
void remove_tree(Node* &root)
{
if (root -> ch[] != NULL)
remove_tree(root -> ch[]);
if (root -> ch[] != NULL)
remove_tree(root -> ch[]);
delete root;
root = NULL;
}
struct
{
int x, y;
bool is_del;
} e[ * maxn];
struct
{
int type, x, p;
} Q[maxn*];
void add_edge(int idx)
{
int fx = find(e[idx].x);
int fy = find(e[idx].y);
if (fx != fy)
{
if (root[fx] -> siz > root[fy] -> siz)
{
pa[fy] = fx;
merge_tree(root[fy], root[fx]);
}
else
{
pa[fx] = fy;
merge_tree(root[fx], root[fy]); }
} }
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int cas = ;
while (~ scanf ("%d%d",&n, &m))
{
if (n == && m == )
break;
for (int i = ; i < n; i++)
{
scanf ("%d", val + + i);
}
for (int i = ; i <= m; i++)
{
scanf ("%d%d", &e[i].x, &e[i].y);
e[i].is_del = false;
}
char op[];
int tot = ;
while (scanf ("%s",op) && op[] != 'E')
{
if (op[] == 'D')
{
scanf ("%d", &Q[tot].x);
Q[tot++].type = ;
e[Q[tot-].x].is_del = true;
}
if (op[] == 'Q')
{
scanf ("%d%d", &Q[tot].x, &Q[tot].p);
Q[tot++].type = ;
}
if (op[] == 'C')
{
int v;
scanf ("%d%d", &Q[tot].x, &v);
Q[tot].p = val[Q[tot].x];
val[Q[tot].x] = v;
Q[tot++].type = ;
}
}
init();
for (int i = ; i < n; i++)
{
if (root[i+] != NULL)
remove_tree(root[i+]);
root[i+] = new Node (val[i+]);
}
for (int i = ; i < m; i++)
{
if (e[i+].is_del == false)
add_edge(i+);
}
ll ans1 = , ans2 = ;
for (int i = tot - ; i >= ; i--)
{
if (Q[i].type == )
{
add_edge(Q[i].x);
}
if (Q[i].type == )
{
ans1 += Get_kth(root[find(Q[i].x)], Q[i].p);
ans2 ++;
}
if (Q[i].type == )
{
int father = find(Q[i].x);
dele (root[father], val[Q[i].x]);
insert (root[father], Q[i].p);
val[Q[i].x] = Q[i].p;
}
}
printf("Case %d: %.6f\n", cas++, 1.0*ans1 / ans2);
}
return ;
}