哎，一道裸splay的題目，網上竟然木有解題報告。我第一次寫splay，犯了很多很多NC的錯誤。。調了有一個下午，最后寫了個測試模塊+生成了隨機數據，才發現錯誤。
說說我的失誤吧。。
1、首先zig zag實現的時候一定要配對，不能亂，加個兒子節點就要把兒子節點的父親節點同時初始化好
2、新加入節點的size域及其祖先的size域名不用調整，會在splay過程中自動修正完畢
3、千萬別要試圖將一顆子樹的根節點插入到另外一棵樹中，以為將兩棵樹給合并住了。。BST的定義是左子樹中的所有節點嚴格小于根節點，而不僅僅是左兒子節點，右子樹亦同。

然后針對本題說說，要倒過來操作，不斷的將連通分支合并，相當于合并兩顆splay，沒有快速的方法，把size小的子樹里的節點一個一個塞到大樹中。記得這個思想MS是09年一場網絡賽里有過的，不過那題的詢問很簡單，恩
代碼
# include <cstdio>
# include <utility>
# include <functional>
# include <cstdlib>
# include <vector>
using namespace std;
struct node
{
    int sz;
    pair<int,int> val;
    node *l,*r,*pre;
    void clear()
    {
        l=r=pre=NULL;
    }
}buff[20005];
inline bool cmp(const pair<int,int> &a,const pair<int,int> &b)
{
    if(a.first!=b.first) return a.first<b.first;
    else return a.second<b.second;
}
inline void update(node *pos)
{
    pos->sz=(pos->l?(pos->l->sz):0)+(pos->r?(pos->r->sz):0)+1;
}
void zig(node *pos)
{
    node *gf=pos->pre->pre,*f=pos->pre;
    (f->l)=(pos->r);
    if(pos->r) (pos->r->pre)=f;
    update(f);
    (pos->r)=f;
    (f->pre)=pos;
    (pos->pre)=gf;
    if(gf&&(gf->l)==f) gf->l=pos;
    else if(gf&&(gf->r)==f) (gf->r)=pos;
}
void zag(node *pos)
{
    node *gf=pos->pre->pre,*f=pos->pre;
    (f->r)=(pos->l);
    if(pos->l) (pos->l->pre)=f;
    update(f);
    f->pre=pos;
    pos->l=f;
    pos->pre=gf;
    if(gf&&gf->l==f) (gf->l)=pos;
    else if(gf&&gf->r==f) (gf->r)=pos;
}
void spaly(node *pos)
{
    while(pos->pre)
    {
        if(pos->pre->pre==NULL)
            if(pos==(pos->pre->l)) zig(pos);
            else zag(pos);
        else
        {
            node *t=pos->pre->pre;
            if(t->l&&pos==(t->l->l))
                zig(pos->pre),zig(pos);
            else if(t->r&&pos==(t->r->r))
                zag(pos->pre),zag(pos);
            else if(t->l&&pos==(t->l->r))
                zag(pos),zig(pos);
            else
            {
                zig(pos);
                zag(pos);
            }
        }
    }
    update(pos);
}
void sub_insert(node *p1,node *p2)
{
    node *pre;
    spaly(p2);
    while(p2)
    {
        pre=p2;
        if(cmp(p1->val,p2->val)) p2=p2->l;
        else p2=p2->r;
    }
    if(cmp(p1->val,pre->val))
        pre->l=p1,p1->pre=pre,spaly(p1);
    else
        pre->r=p1,p1->pre=pre,spaly(p1);
}
void ins(node *p1,node *p2)
{
    if(p1->l) ins(p1->l,p2);
    if(p1->r) ins(p1->r,p2);
    p1->l=p1->r=p1->pre=NULL;
    p1->sz=1;
    sub_insert(p1,p2);
}
void insert(node *p1,node *p2)
{
    spaly(p1),spaly(p2);
    if(p1->sz<p2->sz)
        ins(p1,p2);
    else ins(p2,p1);
}
int select(int pos,int k)
{
    node *p=buff+pos;
    spaly(p);
    if(k>(p->sz)||k<1) return 0;
    else k=(p->sz)+1-k;
    int co=0;
    while(true)
    {
        if(co++>500000) exit(0);
        if((p->l?p->l->sz:0)>=k) p=p->l;
        else if((p->l?p->l->sz:0)+1==k)
           break;
        else k-=(p->l?(p->l->sz):0)+1,p=p->r;
    }
     spaly(p);
     return p->val.first;
}
void change(pair<int,int> val)
{
    node *p=buff+val.second;
    spaly(p);
    p->val=val;
    if(p->l&&p->r)
    {
        node *t1=(p->l),*t2=(p->r);
        (t1->pre)=(t2->pre)=(p->l)=(p->r)=NULL;
        while(t1->r) t1=t1->r;
        spaly(t1);
        (t1->r)=t2;
        (t2->pre)=t1;
        spaly(t2);
        insert(t2,p);
    }
    else if(p->l)
    {
        node *t=p->l;
        (p->l)=(t->pre)=NULL;
        insert(t,p);
    }
    else if(p->r)
    {
        node *t=p->r;
        (p->r)=(t->pre)=NULL;
        insert(t,p);
    }

}
int n,m;
pair<int,int> edge[60005];
bool used[60005];
int father[20005];
pair<int,pair<int,int> >  ask[1000005];
int co=0;
int find(int pos)
{
    if(father[pos]==pos) return pos;
    else return father[pos]=find(father[pos]);
}
int main()
{
    int test=1;
    while(scanf("%d%d",&n,&m)!=EOF&&(n||m))
    {
        for(int i=1;i<=n;i++)
        {
            buff[i].clear();
            buff[i].val.second=i;
            father[i]=i;
            scanf("%d",&buff[i].val.first);
        }
        for(int i=1;i<=m;i++)
        {
            used[i]=true;
            scanf("%d%d",&edge[i].first,&edge[i].second);
        }
        char type[5];
        int number=0;
        co=0;
        while(scanf("%s",type)&&*type!='E')
        {
            pair<int,pair<int,int> > tmp;
            switch(*type)
            {
            case 'D':
                tmp.first=2;
                scanf("%d",&tmp.second.first);
                used[tmp.second.first]=false;
                break;
            case 'C':
            {
                tmp.first=1;
                scanf("%d%d",&tmp.second.second,&tmp.second.first);
                int tt=buff[tmp.second.second].val.first;
                buff[tmp.second.second].val=tmp.second;
                tmp.second.first=tt;
                break;
            }
            case 'Q':
                tmp.first=0;
                number++;
                scanf("%d%d",&tmp.second.first,&tmp.second.second);
                break;
            };
            ask[co++]=tmp;
        }
        for(int i=1;i<=m;i++)
            if(used[i]&&find(edge[i].first)!=find(edge[i].second))
                insert(buff+edge[i].first,buff+edge[i].second),father[find(edge[i].first)]=find(edge[i].second);

           
        double total=0;
        for(int i=co-1;i>=0;i--)
        {
            switch(ask[i].first)
            {
            case 0:
                total+=select(ask[i].second.first,ask[i].second.second);
                break;
            case 1:
                change(ask[i].second);
                break;
            case 2:
                //break;
                if(find(edge[ask[i].second.first].first)!=find(edge[ask[i].second.first].second))
                insert(buff+edge[ask[i].second.first].first,buff+edge[ask[i].second.first].second),
                father[find(edge[ask[i].second.first].first)]=find(edge[ask[i].second.first].second);
                break;
            };
        }
        printf("Case %d: %.6f\n",test++,number?total/number:0);

    }
    return 0;
}