Graph and Queries

Description

You are given an undirected graph with N vertexes and M edges. Every vertex in this graph has an integer value assigned to it at the beginning. You’re also given a sequence of operations and you need to process them as requested. Here’s a list of the possible operations that you might encounter:

1. Deletes an edge from the graph. The format is [D X], where X is an integer from 1 to M, indicating the ID of the edge that you should delete. It is guaranteed that no edge will be deleted more than once.

2. Queries the weight of the vertex with K-th maximum value among all vertexes currently connected with vertex X (including X itself). The format is [Q X K], where X is an integer from 1 to N, indicating the id of the vertex, and you may assume that K will always fit into a 32-bit signed integer. In case K is illegal, the value for that query will be considered as undefined, and you should return 0 as the answer to that query.

3. Changes the weight of a vertex. The format is [C X V ], where X is an integer from 1 to N, and V is an integer within the range [−106 , 106 ].

The operations end with one single character, ‘E’, which indicates that the current case has ended. For simplicity, you only need to output one real number — the average answer of all queries.

Input

There are multiple test cases in the input file. Each case starts with two integers N and M (1 ≤ N ≤ 2 ∗ 104 , 0 ≤ M ≤ 6 ∗ 104 ), the number of vertexes in the graph. The next N lines describes the initial weight of each vertex (−106 ≤ weight[i] ≤ 106 ). The next part of each test case describes the edges in the graph at the beginning. Vertexes are numbered from 1 to N. The last part of each test case describes the operations to be performed on the graph. It is guaranteed that the number of query operations [Q X K] in each case will be in the range [1, 2 ∗ 105 ], and there will be no more than 2 ∗ 105 operations that change the values of the vertexes [C X V ]. There will be a blank line between two successive cases. A case with N = 0, M = 0 indicates the end of the input file and this case should not be processed by your program.

Output

For each test case, output one real number — the average answer of all queries, in the format as indicated in the sample output. Please note that the result is rounded to six decimal places.

Explanation for samples:

For the first sample:

D 3 – deletes the 3rd edge in the graph (the remaining edges are (1, 2) and (2, 3))

Q 1 2 – finds the vertex with the second largest value among all vertexes connected with 1. The answer is 20.

Q 2 1 – finds the vertex with the largest value among all vertexes connected with 2. The answer is 30.

D 2 – deletes the 2nd edge in the graph (the only edge left after this operation is (1, 2))

Q 3 2 – finds the vertex with the second largest value among all vertexes connected with 3. The answer is 0 (Undefined).

C 1 50 – changes the value of vertex 1 to 50. Q 1 1 – finds the vertex with the largest value among all vertex connected with 1. The answer is 50.

E – This is the end of the current test case.

Four queries have been evaluated, and the answer to this case is (20 + 30 + 0 + 50) / 4 = 25.000.

For the second sample, caution about the vertex with same weight: Q 1 1 – the answer is 20 Q 1 2 – the answer is 20 Q 1 3 – the answer is 10

Sample Input

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

Sample Output

Case 1: 25.000000

Case 2: 16.666667

/* * UVaLive 5031 Graph and Queries * 初始给你一个图，执行下面的三个操作 * 1.Delete x : 删除编号为x的边 * 2.Query x,k : 查询和结点x联通的点中，第k大的权值 * 3.Change x,k : 改变结点x的权值为k * 最后输出查询的平均数。 * * 删除不好办，考虑添加，于是反过来做，离线处理，将操作保存下来，然后倒着做 * 用一个treap维护一个联通分量，于是有 * 查询： 即查询第k大，treap很容易实现 * 改变权值：在treap删除原有的权值，在加入新权值即可 * 删除：反过来就是加边，用一个并查集维护联通性，若加的边的两个端点在同一个连通图内， * 不用改变，否则就将一个treap的每个元素加到另一个treap中，并删除它，优化就是用启发式 * 合并，即删除结点较小的那个treap，这样时间复杂度为n1*logn2(n1,n2为treap的节点数) * 对于任意一个结点，当他移动到一个新树时，考虑原树，它的大小至少加了一倍，而节点数为n * 因此至多被移动logn次，移动的代价为logn，这样整体复杂度为O(n*logn*logn). */#include
     
      using namespace std;const int MAXN = 20000+100;const int MAXM = 60000+100;const int MAXO = 500000+100;const int oo=~0u<<1;struct Node{    Node* ch[2];    int val,sz,pri,cnt;//值，结点数，随机优先级，结点重复数；    Node(int v,Node *t):val(v){ ch[0]=ch[1]=t; pri=rand(); sz=cnt=1; }    bool operator < (const Node &rhs) const { return pri
      
       sz + ch[1]->sz + cnt; }}*root[MAXN],*null;//根节点，真实的null指针void Init(){    null=new Node(0,NULL);    null->sz=null->cnt=0;    null->pri=oo;    for(int i=1;i
       
        ch[!d]; o->ch[!d]=k->ch[d]; k->ch[d]=o;    o->push_up(); k->push_up(); o=k;}void Insert(Node* &o,int x){    if(o==null) o=new Node(x,null);    else    {        if(o->val==x)        {            o->cnt++; o->sz++;        }        else        {            bool d=x>o->val;            Insert(o->ch[d],x);            if(o->ch[d]
        
         push_up();        }    }}void Remove(Node* &o,int x){    if(o->val==x)    {        if(o->cnt>1) o->cnt--;        else        {            if(o->ch[0]!=null&&o->ch[1]!=null)            {                bool d=o->ch[0]
         
          ch[1];                Rotate(o,d); Remove(o->ch[d],x);            }            else{                Node* u=o;                if(o->ch[0]==null) o=o->ch[1];                else o=o->ch[0];                delete u;            }        }    }    else    {        bool d=x>o->val;        Remove(o->ch[d],x);    }    if(o!=null) o->push_up();}int Get_Kth(Node* o,int k){    if(o==null||k<=0||k>o->sz) return 0;    int s=o->ch[1]->sz + o->cnt;    if(k>o->ch[1]->sz&&k<=s) return o->val;    else if(k<=o->ch[1]->sz) return Get_Kth(o->ch[1],k);    else return Get_Kth(o->ch[0],k-s);}//并查集int fa[MAXN];int findroot(int x){    return fa[x]==x? x:fa[x]=findroot(fa[x]);}struct Operate{    int type;    int x,k;}op[MAXO];struct Edge{    int from,to;    bool flag;//是否被移除}edge[MAXM];int val[MAXN],n,m;void Merge_Tree(Node* &aa,int k){    if(aa==null) return;    int cnt=aa->cnt;    while(cnt--) Insert(root[k],aa->val);    Merge_Tree(aa->ch[0],k);    Merge_Tree(aa->ch[1],k);    delete aa;    //Remove(aa,aa->val);    aa=null;}void Clear_Tree(Node* &aa){    if(aa==null) return;    Clear_Tree(aa->ch[0]);    Clear_Tree(aa->ch[1]);    delete aa;    aa=null;}void Add_Edge(int x){    int u=findroot(edge[x].from);    int v=findroot(edge[x].to);    if(u!=v)    {        if(root[u]->sz>root[v]->sz)        {            fa[v]=u;            Merge_Tree(root[v],u);        }        else        {            fa[u]=v;            Merge_Tree(root[u],v);        }    }}void Change_Weight(int x,int v){    int u=findroot(x);    Remove(root[u],val[x]);    Insert(root[u],v);    val[x]=v;}int ans_cnt;long long ans_tot;void Query_Tot(int x,int k){    ans_cnt++;    int u=findroot(x);    ans_tot+=(long long)(Get_Kth(root[u],k));}void Prep(){    for(int i=1;i<=n;i++) fa[i]=i;    for(int i=1;i<=n;i++) Clear_Tree(root[i]);    for(int i=1;i<=n;i++) Insert(root[i],val[i]);    for(int i=1;i<=m;i++) if(!edge[i].flag) Add_Edge(i);}void work(){    char str[5];    int x,p;    int iCase=0;    while(scanf("%d%d",&n,&m)==2)    {        iCase++;        if(n==0&&m==0) break;        for(int i=1;i<=n;i++) scanf("%d",&val[i]);        for(int i=1;i<=m;i++) scanf("%d%d",&edge[i].from,&edge[i].to);        for(int i=1;i<=m;i++) edge[i].flag=false;        int tot=1;        while(1)        {            scanf("%s",str);            if(str[0]=='E') break;            if(str[0]=='D')            {                scanf("%d",&x);                edge[x].flag=true;                op[tot].type=1;                op[tot].x=x;                tot++;            }            else if(str[0]=='Q')            {                scanf("%d%d",&x,&p);                op[tot].type=2;                op[tot].x=x;                op[tot].k=p;                tot++;            }            else if(str[0]=='C')            {                scanf("%d%d",&x,&p);                op[tot].type=3;                op[tot].x=x;                op[tot].k=val[x];                val[x]=p;                tot++;            }        }        Prep();        ans_cnt=ans_tot=0;        for(int i=tot-1;i>=1;i--)        {            if(op[i].type==1) Add_Edge(op[i].x);            else if(op[i].type==2) Query_Tot(op[i].x,op[i].k);            else if(op[i].type==3) Change_Weight(op[i].x,op[i].k);        }        printf("Case %d: %.6lf\n",iCase,(double)ans_tot/(double)ans_cnt);    }}int main(){    //freopen("in.txt","r",stdin);    Init();    work();    return 0;}