# UVaLive 5031 Graph and Queries (Treap)

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

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;
}
{
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]);
}
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--)
{
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;
}
```