【左偏树】[LuoguP1456] Monkey King

客官°小女子只卖身不卖艺 2023-06-01 06:08 25阅读 0赞

多...多组数据...

awsl

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

左偏树模板？

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

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

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 }

转载于:https://www.cnblogs.com/zhenglw/p/11243043.html