学步园

题目大意：有一个无向图，n个点，m条边，每个点有一个权值，有四种操作：（1）D X 表示把删除第 X 条边（2）Q X K 表示询问与节点 X 连通的所有点中，包括 X 点，第 K 大的点的权值。（3）C X V 表示将第 X 个点的权值改为 V 。（4）E 表示结束操作。让你输出所有询问操作的值的平均值。

思路：正着不好处理，我们倒着来，先把所有操作后的最终图求出来，然后用名次树，对于每一个连通分量建一棵名次树，对于题目中的操作，我们只需要做 删点，插入点，将两棵名次树合并、查询第k大点 这四个操作就可以了，其中合并两棵树时需要注意，设两棵树的节点数为 n1，n2，假设把n1插入到n2，复杂度为 n1*logn2，要把节点数少的加到多的那里去。启发式合并，总时间复杂度为O（n*logn*logn）。

敲的第一道treap题，调试真心好麻烦。。 代码长长一坨，注意要分清各个部分。。= =

代码如下：

#include<cstdio>
#include<cstdlib>

struct Node
{
    Node* ch[2];
    int v,r;//节点权值、随机优先级
    int size;//子树大小，即节点总数
    Node(int v) : v(v) {ch[0] = ch[1] = NULL;r = rand();size = 1;}
    bool operator < (const Node &tmp) const
    {
        return r < tmp.r;
    }
    int cmp(int x)
    {
        if(x == v) return -1;
        else 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(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);
        return ;
    }
    int d = (x < o->v )? 0: 1;
    insert(o->ch[d],x);
    if(o < o->ch[d]) rotate(o,d^1);
    o->maintain();
}

void remove(Node* &o,int x)
{
    int d = o->cmp(x);
    if(d == -1)
    {
        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
        {
            Node* u = o;
            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 debug(Node* o)
{
    if(o == NULL) return ;
    printf("%d(",o->v);
    if(o->ch[0]!=NULL) printf("%d,",o->ch[0]->v);
    else printf("NULL,");
    if(o->ch[1]!=NULL) printf("%d",o->ch[1]->v);
    else printf("NULL");
    puts(")");
    if(o->ch[0]!=NULL) debug(o->ch[0]);
    if(o->ch[1]!=NULL) debug(o->ch[1]);
}

#include<cstring>
#include<algorithm>
using namespace std;

typedef __int64 lld;

const int MAXN = 22222;
const int MAXM = 66666;

struct Command
{
    char op;
    int x,p;
    Command(){}
    Command(char c,int a,int b) : op(c),x(a),p(b) {}
} command[555555];

int removed[MAXM];
int from[MAXM],to[MAXM],w[MAXN],fa[MAXN];;

//名次树

Node* root[MAXN];

int kth(Node* &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 remove_tree(Node* &o)
{
    if(o->ch[0] != NULL) remove_tree(o->ch[0]);
    if(o->ch[1] != NULL) remove_tree(o->ch[1]);
    delete o;
    o = NULL;
}

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 init_treap(int n)
{
    for(int i = 1;i<=n;i++)
    {
        fa[i] = i;
        if(root[i] != NULL) remove_tree(root[i]);
        root[i] = new Node(w[i]);
    }
}

// 主程序部分

int find_set(int x)
{
    return x == fa[x] ? x : find_set(fa[x]);
}

void change_w(int x,int v)
{
    int u = find_set(x);
    remove(root[u],w[x]);
    insert(root[u],v);
    w[x] = v;
}

lld query(int x,int k)
{
    return (lld)kth(root[find_set(x)],k);
}

void add_edge(int id)
{
    int a = find_set(from[id]),b = find_set(to[id]);
    if(a!=b)
    {
        if(root[a]->size < root[b]->size){fa[a] = b;mergeto(root[a],root[b]);} //将小的合并到大的，否则会TLE
        else {fa[b] = a;mergeto(root[b],root[a]);}
    }
}

char str[11];

int main()
{
    int cas = 0;
    int n,m;
    while(~scanf("%d%d",&n,&m)&&(n+m))
    {
        for(int i = 1;i<=n;i++)
            scanf("%d",&w[i]);
        for(int i = 1;i<=m;i++)
            scanf("%d%d",&from[i],&to[i]);
        memset(removed,0,sizeof(removed));
        int query_cnt = 0;
        int x,p;
        int cc = 0;
        for(;;)
        {
            scanf("%s",str);
            if(str[0] == 'E') break;
            else if(str[0] == 'D')
            {
                scanf("%d",&x);
                removed[x] = 1;
            }
            else if(str[0] == 'Q')
            {
                scanf("%d%d",&x,&p);
                query_cnt ++;
            }
            else
            {
                int v;
                scanf("%d%d",&x,&v);
                p = w[x];
                w[x] = v;
            }
            command[cc++] = Command(str[0],x,p);
        }
        init_treap(n);
        for(int i = 1;i<=m;i++)
            if(!removed[i]) add_edge(i);
        /*for(int i = 1;i<=n;i++)
        {
            int u = find_set(i);
            printf("i = %d,u = %d\n",i,u);
            debug(root[u]);
        }*/
        lld ans = 0;//会爆int，记得要lld
        for(int i = cc-1;i>=0;i--)
        {
            if(command[i].op == 'D') add_edge(command[i].x);
            else if(command[i].op == 'Q') ans += query(command[i].x,command[i].p);
            else change_w(command[i].x,command[i].p);
        }
        //printf("%I64d,%d\n",ans,query_cnt);
        printf("Case %d: %.6f\n",++cas,ans/(double)query_cnt);
    }
    return  0;
}