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 ",iCase,(double)ans_tot/(double)ans_cnt); } } int main() { //freopen("in.txt","r",stdin); Init(); work(); return 0; }