hdu 3726

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <vector>
  6 
  7 #define KT ch[ch[root][1]][0]
  8 #define LC ch[x][0]
  9 #define RC ch[x][1]
 10 #define N 61001
 11 #define M 61000
 12 #define Q 500000
 13 using namespace std;
 14 
 15 
 16 int fa[N];
 17 int ch[N][2];
 18 int sz[N];
 19 int top1;
 20 int top2;
 21 int ss[N];
 22 int que[N];
 23 int nodque[N],top3;
 24 int val[N];
 25 int nodbelong[N];
 26 int ini[N];
 27 const int inf=1e9;
 28 vector<int> g[N];
 29 struct SplayTree{
 30     int root;
 31     void rotate(int x,bool f){
 32         int y=fa[x];
 33         int z=fa[y];
 34         pushdown(y);
 35         pushdown(x);
 36         ch[y][!f]=ch[x][f];
 37         fa[ch[x][f]]=y;
 38         fa[x]=z;
 39         if (z) {
 40             ch[z][ch[z][1]==y] = x;
 41         }
 42         ch[x][f] = y;
 43         fa[y]=x;
 44         pushup(y);
 45     }
 46     void splay(int x, int g) {
 47         int y = fa[x];
 48         pushdown(x);
 49         while(y!=g){
 50             int z= fa[y];
 51             bool f = (ch[y][0]==x);
 52             if(z != g && f == (ch[z][0]==y)){
 53                 rotate(y,f);
 54             }
 55             rotate(x,f);
 56             y=fa[x];
 57         }
 58         pushup(x);
 59         if(g==0) root = x;
 60     }
 61     void rotateTo(int k,int g) {
 62         int x=root;
 63         pushdown(x);
 64         while(sz[LC] != k){
 65             if(k<sz[LC]){
 66                 x=LC;
 67             }else{
 68                 k -= sz[LC] + 1;
 69                 x = RC;
 70             }
 71             pushdown(x);
 72         }
 73         splay(x,g);
 74     }
 75     void build(int l,int r,int f){
 76         if(l>r){
 77             return ;
 78         }
 79         int x = (l + r) >> 1;
 80         LC = (x - 1 >= l)? (x - 1 + l)>> 1 :0;
 81         RC = (r >= x + 1)? (x + 1 + r)>> 1 :0;
 82         fa[x] = f;
 83         build(l,x - 1,x);
 84         build(x + 1,r,x);
 85         pushup(x);
 86     }
 87     void erase(int x){
 88         if(x==0)
 89             return;
 90         int father= fa[x];
 91         int head = 0, tail=0;
 92         for(que[tail++] =x ; head < tail; head++){
 93             ss[top2++] = que[head];
 94             if(ch[que[head]][0]){
 95                 que[tail++]=ch[que[head]][0];
 96             }
 97             if(ch[que[head]][1]){
 98                 que[tail++] = ch[que[head]][1];
 99             }
100         }
101         ch[father][ch[father][1]==x]=0;
102         pushup(father);
103     }
104     void makeTree(int &x, int l, int r, int f ,vector<int>& g){
105         if(l > r){
106             return;
107         }
108         int m=(l+r)>>1;
109         newNode(x, ini[g[m]],g[m]);
110         makeTree(LC,l,m-1,x,g);
111         makeTree(RC,m+1,r,x,g);
112         fa[x]=f;
113         pushup(x);
114     }
115     void treaval(int x){
116         if (x) {
117             pushdown(x);
118             treaval(LC);
119             printf("@%d",val[x]);
120 
121             //ans[cnt++]=val[x];
122             treaval(RC);
123         }
124     }
125     void dfs(int x){
126         if (x) {
127             pushdown(x);
128             dfs(LC);
129             nodque[top3++]=x;
130             dfs(RC);
131         }
132     }
133     void newNode(int &x,int c,int id){
134         if(id){
135             x=id;//直接另节点号一致
136         }
137         else if(top2){
138             x = ss[--top2];
139         } else {
140             x = ++top1;//top1从n+1，开始
141         }
142         LC = 0;
143         RC = 0;
144         fa[x] =0;
145         sz[x] = 1;
146 
147         val[x]=c;
148     }
149     void pushdown(int x){
150 
151     }
152     void pushup(int x){
153         sz[x]=1+sz[LC]+sz[RC];
154     }
155 
156     void debug(){
157         treaval(root);
158         cout<<endl;
159     }
160     void cutTo(int l,int r,int c){
161         rotateTo(l-1,0);
162         rotateTo(r+1,root);
163         int tmp=KT;
164         KT=0;
165         pushup(ch[root][1]);
166         pushup(root);
167 
168         rotateTo(c,0);
169         rotateTo(c+1,root);
170         fa[tmp]=ch[root][1];
171         KT=tmp;
172         pushup(ch[root][1]);
173         pushup(root);
174     }
175 
176     void init(vector<int>&g){
177 
178         root=0;
179         int n=g.size();
180         newNode(root,inf,0);
181         newNode(ch[root][1],-inf,0);
182         fa[ch[root][1]]=root;
183         //for(int i=1;i<=n;i++)scanf("%d",&num[i]);
184         makeTree(KT,0,n-1,ch[root][1],g);
185         pushup(ch[root][1]);
186         pushup(root);
187     }
188     int size(){
189         return sz[root]-2;
190     }
191     int find(int x,int v,int cur){
192         if(val[x]>=v){
193             cur=x;
194             return RC?find(RC,v,cur):cur;
195         }else{
196             return LC?find(LC,v,cur):cur;
197         }
198 //        if(val[LC]<v){
199 //            return find(LC,v);
200 //        }else if(val[RC]>v){
201 //            return find(RC,v);
202 //        }else
203 //            return val[x]<v?LC:RC;
204     }
205     void insert(int y){//将y节点插入splay
206         int x=find(root,val[y],root);
207         splay(x,0);
208         int s=sz[LC]+1;
209         rotateTo(s,root);
210         fa[y]=ch[root][1];
211         ch[y][0]=0;
212         ch[y][1]=0;
213         KT=y;
214         sz[y]=1;
215         pushup(ch[root][1]);
216         pushup(root);
217     }
218     void merge(SplayTree spt){
219         top3=0;
220         spt.dfs(spt.root);
221         rotateTo(1,0);
222         int tmp=nodbelong[root];
223         for(int i=1;i<top3-1;i++){
224             insert(nodque[i]);
225             nodbelong[nodque[i]]=tmp;
226         }
227     }
228     void change(int x,int k){
229         splay(x,0);
230         int s=sz[LC];
231         rotateTo(s-1,0);
232         rotateTo(s+1,root);
233 
234         KT=0;
235         pushup(ch[root][1]);
236         pushup(root);
237 
238         val[x]=k;
239         insert(x);
240     }
241     int query(int k){
242         if(k>size()||k<=0)return 0;
243         rotateTo(k,0);
244         return val[root];
245     }
246 
247 }spt[N];
248 
249 struct edge{
250     int flag;
251     int to;
252     int next;
253 }e[M<<1];
254 int head[N],num;
255 void _add(int u,int v){
256     e[num].flag=0;
257     e[num].to=v;
258     e[num].next=head[u];
259     head[u]=num++;
260 }
261 void add(int u,int v){
262     _add(u,v);
263     _add(v,u);
264 }
265 struct Ques{
266     char op;
267     int x,k;
268     void set(char o,int xx,int kk){
269         op=o;
270         x=xx;
271         k=kk;
272     }
273 }questa[Q];
274 int top4;
275 int vis[N];
276 
277 void dfs(int x,int id){
278     vis[x]=1;
279     nodbelong[x]=id;
280     for(int i=head[x];i!=-1;i=e[i].next)if(!e[i].flag&&!vis[e[i].to]){
281         dfs(e[i].to,id);
282     }
283 }
284 int cmp(int i,int j){
285     return ini[i]>ini[j];
286 }
287 void init(int n,int m){
288     memset(head,-1,sizeof(int)*(n+1));
289     num=top4=0;
290     top1=n;top2=0;
291     memset(vis,0,sizeof(int)*(n+1));
292 }
293 void solve( int n,int m){
294 
295     int u,v;
296     int x,k;
297     char op[10];
298 
299     init(n,m);
300     for(int i=1;i<=n;i++){
301         scanf("%d",&ini[i]);
302     }
303     for(int i=0;i<m;i++){
304         scanf("%d%d",&u,&v);
305         add(u,v);
306     }
307     top4=0;
308     while(scanf("%s",op),op[0]!=‘E‘){
309         if(op[0]==‘D‘){
310             scanf("%d",&x);
311             int id=(x-1)*2;
312             questa[top4++].set(op[0],e[id].to,e[id^1].to);
313             e[id].flag=1;
314             e[id^1].flag=1;
315         }else if(op[0]==‘Q‘){
316             scanf("%d%d",&x,&k);
317             questa[top4++].set(op[0],x,k);
318         }else{
319             scanf("%d%d",&x,&k);
320             questa[top4++].set(op[0],x,ini[x]);
321             ini[x]=k;
322         }
323     }
324     int cnt=0;
325     for(int i=1;i<=n;i++)if(!vis[i]){
326         dfs(i,cnt++);
327     }
328     for(int i=1;i<=n;i++){
329         g[nodbelong[i]].push_back(i);
330     }
331     for(int i=0;i<cnt;i++){
332         sort(g[i].begin(),g[i].end(),cmp);
333 //        for(int j=g[i].size()-1;j>=0;j--){
334 //            cout<<g[i][j]<<" ";
335 //        }
336 //        cout<<endl;
337     }
338     for(int i=0;i<cnt;i++){
339         spt[i].init(g[i]);
340     }
341 //    for(int i=0;i<cnt;i++)
342 //        cout<<spt[i].size()<<endl;
343     double ans=0;
344     int ret=0;
345     while(top4--){
346         char op=questa[top4].op;
347         x=questa[top4].x;k=questa[top4].k;
348         if(op==‘D‘){
349             int id1=nodbelong[x];
350             int id2=nodbelong[k];
351             int sz1=spt[id1].size();
352             int sz2=spt[id2].size();
353             if(id1==id2)continue;
354             if(sz1>sz2){
355                 spt[id1].merge(spt[id2]);
356             }else{
357                 spt[id2].merge(spt[id1]);
358             }
359         }else if(op==‘C‘){
360             int id=nodbelong[x];
361 
362             spt[id].change(x,k);
363         }else{
364             int id=nodbelong[x];
365             //spt[id].debug();
366             //int t=spt[id].query(k);
367             ans+=spt[id].query(k);
368             //cout<<t<<endl;
369             ret++;
370         }
371     }
372     printf("%.6lf\n",(double)ans/ret);
373     for(int i=0;i<cnt;i++)g[i].clear();
374 }
375 int main()
376 {
377     int n,m;
378 
379     int cas=1;
380     while(scanf("%d%d",&n,&m),n||m){
381         printf("Case %d: ",cas++);
382         solve(n,m);
383     }
384     return 0;
385 }