UVaLive 5031 Graph and Queries (Treap)

Datetime:2016-08-23 01:17:38          Topic:          Share

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<bits/stdc++.h>
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<rhs.pri; }
    void push_up(){ sz = ch[0]->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<MAXN;i++) root[i]=null;
    //root=null;
}
void Rotate(Node* &o,bool d)
{
    Node* k=o->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]<o) Rotate(o,!d);
            o->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]<o->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;
}