白书原题源代码
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
using namespace std;
#define N 20005
struct Treap{
Treap *ch[2];
int r; //数字越大，优先级越高
int v; //值
int size; //子树的节点数
Treap(int v):v(v) { ch[0]=ch[1]=NULL; r=rand(); size=1;}
bool operator < (const Treap& rhs) const{
return r < rhs.r;
}
int cmp(int x) const{
if(x == v)return -1;
return x < v ? 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* &o, int d){
Treap* k = o->ch[d^1]; o->ch[d^1] = k->ch[d]; k->ch[d] = o;
o->maintain(); k->maintain(); o = k;
}
void insert(Treap* &o, int x){
if(o == NULL) o = new Treap(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(Treap* &o, int x){
int d = o->cmp(x);
if(d == -1){
Treap* 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();
}
#define M 60005
struct Query{
char Type;
int x, p;
Query(char a=0,int b=0,int c=0):Type(a),x(b),p(c){}
}query[500010];
int n, m, weight[N], from[M], to[M], removed[M];
int fa[N];
int findset(int x){return x==fa[x]? x : fa[x] = findset(fa[x]);}
Treap* root[N];
int kth(Treap* o, int k){
if(o == NULL || k<=0 || k> o->size) return 0;
int s = (o->ch[1] == NULL ? 0 : o->ch[1]->size);
if( k == s+1) return o->v;
else if(k <= s) return kth(o->ch[1], k);
else return kth(o->ch[0], k - s - 1);
}
void mergeto(Treap* &src, Treap* &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 removetree(Treap* &x){
if(x->ch[0] != NULL) removetree(x->ch[0]);
if(x->ch[1] != NULL) removetree(x->ch[1]);
delete x;
x = NULL;
}
void add_edge(int x){
int u = findset(from[x]), v = findset(to[x]);
if(u != v){
if(root[u]->size < root[v]->size) { fa[u] = v; mergeto(root[u], root[v]);}
else { fa[v] = u; mergeto(root[v], root[u]);}
}
}
int query_cnt;
long long query_tot;
void Q(int x, int k){
query_cnt++;
query_tot += kth(root[findset(x)], k);
}
void change_weight(int x, int v){
int u = findset(x);
remove(root[u], weight[x]);
insert(root[u], v);
weight[x] = v;
}
int main(){
int Cas = 0;
while(scanf("%d %d", &n, &m), n+m){
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]);
memset(removed, 0, sizeof(removed));
int c = 0;
while(1){
char type; scanf(" %c", &type); if(type == ‘E‘)break;
int x, p = 0, v = 0;
scanf("%d",&x);
if(type == ‘D‘) removed[x] = 1;
if(type == ‘Q‘) scanf("%d", &p);
if(type == ‘C‘) scanf("%d", &v);
if(type == ‘C‘) {
scanf("%d", &v);
p = weight[x];
weight[x] = v;
}
query[c++] = Query(type, x, p);
}
for(int i = 1; i <= n; i++) {
fa[i] = i; if(root[i] != NULL) removetree(root[i]);
root[i] = new Treap(weight[i]);
}
for(int i =1; i <= m; i++) if(!removed[i]) add_edge(i);
query_tot = query_cnt = 0;
for(int i = c-1; i >= 0; i--) {
if(query[i].Type == ‘D‘) add_edge(query[i].x);
if(query[i].Type == ‘Q‘) Q(query[i].x, query[i].p);
if(query[i].Type == ‘C‘) change_weight(query[i].x, query[i].p);
}
printf("Case %d: %.6lf\n", ++Cas, query_tot / (double)query_cnt);
}
return 0;
}
/*
3 3
10
20
30
1 2
2 3
1 3
D 3
Q 1 2
Q 2 1
D 2
Q 3 2
C 1 50
Q 1 1
E
3 3
10
20
20
1 2
2 3
1 3
Q 1 1
Q 1 2
Q 1 3
E
0 0
*/