TJU 3755 - Graph and Queries

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAXN 20001
#define MAXM 60000
#define MAXQ 460000

long long seed = 47;

long long my_rand(){
    seed = (seed * 279470273) % 4294967291LL;
    return seed;
}

struct item{
    int key;
    long long prior;
    item *l,*r;
    int sons;

    item(){}

    item(int key) : key(key), l(NULL), r(NULL){
        prior = my_rand();
    }

    ~item(){
        if(l) delete l;
        if(r) delete r;
    }
};

item* T[MAXN];
item* aux;

void fix(item* t){
    if(!t) return;

    t->sons = (t->l ? t->l->sons + 1 : 0) +
        (t->r ? t->r->sons + 1 : 0);
}

void split(item* t, int key, item* &l, item* &r){
    if(!t)
        l = r = NULL;
    else if(key < t->key)
        split(t->l,key,l,t->l), r = t;
    else
        split(t->r,key,t->r,r), l = t;

    fix(t);
}

void insert(item* &t, item* it){
    if(!t)
        t = it;
    else if(it->prior > t->prior)
        split(t, it->key, it->l, it->r), t = it;
    else
        insert(it->key < t->key ? t->l : t->r, it);

    fix(t);
}

void merge(item* &t, item* l, item* r){
    if(!l || !r)
        t = l ? l : r;
    else if(l->prior > r->prior)
        merge(l->r, l->r, r), t = l;
    else
        merge(r->l, l, r->l), t = r;

    fix(t);
}

void erase(item* &t, int key){
    if(t->key == key)
        merge(t, t->l, t->r);
    else
        erase(key < t->key ? t->l : t->r, key);

    fix(t);
}

item* unite(item* l, item* r){
    if(!l || !r) return l ? l : r;
    if(l->prior < r->prior) swap (l, r);

    item *lt,*rt;

    split(r, l->key, lt, rt);
    l->l = unite(l->l, lt);
    l->r = unite(l->r, rt);

    return l;
}

int get_Kth(item* &t, int K){
    int x = (t->l == NULL? 0 : 1 + t->l->sons);

    if(K == x) return t->key;
    if(K < x) return get_Kth(t->l,K);
    return get_Kth(t->r,K - x - 1);
}

int w[MAXN],parent[MAXN],sz[MAXN];
int u[MAXM],v[MAXM];
bool ins[MAXM];

int Find(int x){
    if(parent[x] != x) parent[x] = Find(parent[x]);
    return parent[x];
}

void Union(int x, int y){
    x = Find(x); y = Find(y);

    if(x != y){
        parent[x] = y;
        sz[y] += sz[x];
    }
}

int Q,type[MAXQ],param1[MAXQ],param2[MAXQ];

int main(){
    int tc = 1,N,M;
    char s[2];

    while(true){
        scanf("%d %d",&N,&M);
        if(N == 0) break;

        for(int i = 1;i <= N;++i)
            scanf("%d",&w[i]);

        memset(ins,true,sizeof ins);

        for(int i = 1;i <= M;++i)
            scanf("%d %d",&u[i],&v[i]);

        int cont = 0;
        Q = 0;

        while(true){
            scanf("%s",s);

            if(s[0] == 'E') break;

            if(s[0] == 'D'){
                type[Q] = 0;
                scanf("%d",&param1[Q]);
                ins[ param1[Q] ] = false;
            }

            if(s[0] == 'Q'){
                type[Q] = 1;
                scanf("%d %d",&param1[Q],&param2[Q]);
                ++cont;
            }

            if(s[0] == 'C'){
                type[Q] = 2;
                scanf("%d %d",&param1[Q],&param2[Q]);
                swap(param2[Q],w[ param1[Q] ]);
            }

            ++Q;
        }

        for(int i = 1;i <= N;++i){
            parent[i] = i;
            sz[i] = 1;
        }

        for(int i = 1;i <= M;++i)
            if(ins[i]) Union(u[i],v[i]);

        for(int i = 1;i <= N;++i)
            if(parent[i] == i)
                T[i] = new item(10000000);

        for(int i = 1;i <= N;++i)
            insert(T[ Find(i) ],new item(w[i]));

        long long sum = 0;

        for(int q = Q - 1;q >= 0;--q){
            if(type[q] == 0){
                int e = param1[q];

                u[e] = Find(u[e]); v[e] = Find(v[e]);

                if(u[e] != v[e]){
                    Union(u[e],v[e]);
                    aux = unite(T[ u[e] ],T[ v[e] ]);
                    T[ v[e] ] = aux;
                }
            }

            if(type[q] == 1){
                int r = Find(param1[q]);

                if(param2[q] <= sz[r])
                    sum += get_Kth(T[r],sz[r] - param2[q]);
            }

            if(type[q] == 2){
                erase(T[ Find(param1[q]) ],w[ param1[q] ]);
                insert(T[ Find(param1[q]) ],new item(param2[q]));
                w[ param1[q] ] = param2[q];
            }
        }

        for(int i = 1;i <= N;++i)
            if(parent[i] == i)
                delete T[i];

        printf("Case %d: %.6f\n",tc++,(double)sum / cont);
    }

    return 0;
}