【左偏树】[LuoguP1456] Monkey King

 1 // luogu-judger-enable-o2
 2 #include<bits/stdc++.h>
 3 #define writeln(x)  write(x),puts("")
 4 #define writep(x)   write(x),putchar(' ')
 5 using namespace std;
 6 inline int read(){
 7     int ans=0,f=1;char chr=getchar();
 8     while(!isdigit(chr)){if(chr=='-') f=-1;chr=getchar();}
 9     while(isdigit(chr)){ans=(ans<<3)+(ans<<1)+chr-48;chr=getchar();}
10     return ans*f;
11 }void write(int x){
12     if(x<0) putchar('-'),x=-x;
13     if(x>9) write(x/10);
14     putchar(x%10+'0');
15 }const long M=1e5+5;
16 int son[M][2],dis[M],v[M],rt[M],n,m;
17 int Find(int x){if(rt[x]==x)return x;return rt[x]=Find(rt[x]);}
18 #define ls son[x][0]
19 #define rs son[x][1]
20 int Merge(int x,int y){
21     if(!x||!y) return x+y;
22     if(v[x]<v[y]) swap(x,y);
23     rs=Merge(rs,y);
24     if(dis[ls]<dis[rs]) swap(ls,rs);
25     rt[ls]=rt[rs]=rt[x]=x;
26     dis[x]=dis[rs]+1;
27     return x;
28 }
29 void Pop(int x){
30     v[x]=-1;rt[ls]=ls,rt[rs]=rs;
31     rt[x]=Merge(ls,rs);
32 }
33 signed main(){
34     while(~scanf("%d",&n)){
35         memset(son,0,sizeof(son));
36         memset(v,0,sizeof(v));
37         memset(dis,0,sizeof(dis));
38         dis[0]=-1;
39         for(int i=1;i<=n;i++)    rt[i]=i,v[i]=read();
40         m=read();
41         while(m--){
42             int x=read(),y=read();
43             int fx=Find(x),fy=Find(y);
44             if(fx==fy) puts("-1");
45             else{
46                 v[fx]>>=1,v[fy]>>=1;
47                 int tx=Merge(son[fx][0],son[fx][1]);
48                 rt[son[fx][0]]=rt[son[fx][1]]=tx;
49                 son[fx][0]=son[fx][1]=dis[fx]=0;
50                 rt[fx]=fx;
51                 int ty=Merge(son[fy][0],son[fy][1]);
52                 rt[son[fy][0]]=rt[son[fy][1]]=ty;
53                 son[fy][0]=son[fy][1]=dis[fy]=0;
54                 rt[fy]=fy;
55                 int root=Merge(tx,ty);
56                 root=Merge(fx,root);
57                 root=Merge(fy,root);
58                 cout<<v[root]<<endl;
59             }
60         }
61     }
62     return 0;
63 }