【左偏树】[LuoguP1456] Monkey King

多...多组数据...

awsl

死命的MLE，原来是忘记清空数组了....

左偏树模板？

对于每一个操作，我们把两个节点$x,y$的祖先$fx,fy$找到，然后把他们的左右儿子分别合并

最后把$v[fx],v[fy]$分别>>1再合并回去就好了

 // luogu-judger-enable-o2

 #include<bits/stdc++.h>

 #define writeln(x)  write(x),puts("")

 #define writep(x)   write(x),putchar(' ')

 using namespace std;

 inline int read(){

     int ans=,f=;char chr=getchar();

     while(!isdigit(chr)){if(chr=='-') f=-;chr=getchar();}

     while(isdigit(chr)){ans=(ans<<)+(ans<<)+chr-;chr=getchar();}

     return ans*f;

 }void write(int x){

     if(x<) putchar('-'),x=-x;

     if(x>) write(x/);

     putchar(x%+'');

 }const long M=1e5+;

 int son[M][],dis[M],v[M],rt[M],n,m;

 int Find(int x){if(rt[x]==x)return x;return rt[x]=Find(rt[x]);}

 #define ls son[x][0]

 #define rs son[x][1]

 int Merge(int x,int y){

     if(!x||!y) return x+y;

     if(v[x]<v[y]) swap(x,y);

     rs=Merge(rs,y);

     if(dis[ls]<dis[rs]) swap(ls,rs);

     rt[ls]=rt[rs]=rt[x]=x;

     dis[x]=dis[rs]+;

     return x;

 }

 void Pop(int x){

     v[x]=-;rt[ls]=ls,rt[rs]=rs;

     rt[x]=Merge(ls,rs);

 }

 signed main(){

     while(~scanf("%d",&n)){

         memset(son,,sizeof(son));

         memset(v,,sizeof(v));

         memset(dis,,sizeof(dis));

         dis[]=-;

         for(int i=;i<=n;i++)    rt[i]=i,v[i]=read();

         m=read();

         while(m--){

             int x=read(),y=read();

             int fx=Find(x),fy=Find(y);

             if(fx==fy) puts("-1");

             else{

                 v[fx]>>=,v[fy]>>=;

                 int tx=Merge(son[fx][],son[fx][]);

                 rt[son[fx][]]=rt[son[fx][]]=tx;

                 son[fx][]=son[fx][]=dis[fx]=;

                 rt[fx]=fx;

                 int ty=Merge(son[fy][],son[fy][]);

                 rt[son[fy][]]=rt[son[fy][]]=ty;

                 son[fy][]=son[fy][]=dis[fy]=;

                 rt[fy]=fy;

                 int root=Merge(tx,ty);

                 root=Merge(fx,root);

                 root=Merge(fy,root);

                 cout<<v[root]<<endl;

             }

         }

     }

     return ;

 }