zcmimi's blog
avatar
zc
2020-04-07 20:04:00
  • 本文总阅读量
查看原题

点击跳转

fhqtreap做法

在普通fhqtreap的基础上记录节点的父亲

M x y: 一直向上走就可以找到根,然后合并即可

D x: 求出x的排名,然后按排名分裂即可

Q x y: 求出x,y排名,分裂,得出答案,再合并回去

#include<bits/stdc++.h>
#pragma GCC optimize(3)
#define il __inline__ __attribute__ ((always_inline))
typedef long long ll;
namespace IO{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;il char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}il void in(char &ch){if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)__=1;else ch=c;}il void in(char *ch){*ch='\0';if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF){__=1;return;}*ch=c;ch++;while((c=gc())!=EOF&&!isspace(c))*ch=c,ch++;if(c==EOF)__=1;*ch='\0';}template<typename T>il void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>il void in(T &x,arr & ... y){in(x),in(y...);}const char ln='\n';static char out_buf[str],*out_s=out_buf,*out_t=out_buf+str;il void flush(){fwrite(out_buf,1,out_s-out_buf,stdout);out_s=out_buf;}il void pt(char c){(out_s==out_t)?(fwrite(out_s=out_buf,1,str,stdout),*out_s++=c):(*out_s++=c);}il void out(const char* s){while(*s)pt(*s++);}il void out(char* s){while(*s)pt(*s++);}il void out(char c){pt(c);}template<typename T>il void out(T x){if(!x){pt('0');return;}if(x<0)pt('-'),x=-x;char a[50],t=0;while(x)a[t++]=x%10,x/= 10;while(t--)pt(a[t]+'0');}template<typename T,typename ... arr>il void out(T x,arr & ... y){out(x),out(y...);}}using namespace IO;
const int N=200001;
int n,q,ls[N],rs[N],f[N],rnd[N],v[N],sz[N];
ll s[N];
il int rand(){static int seed=233;return seed=(int)seed*482711LL%n; }
il void pu(int x){
    s[x]=s[ls[x]]+s[rs[x]]+v[x];
    sz[x]=sz[ls[x]]+sz[rs[x]]+1;
    f[ls[x]]=f[rs[x]]=x;
}
void sl(int &x,int &y,int rt,int k){
    if(!rt)return void(x=y=0);
    if(sz[ls[rt]]>=k)y=rt,sl(x,ls[y],ls[y],k);
    else x=rt,sl(rs[x],y,rs[x],k-sz[ls[x]]-1);
    pu(rt);
}
int mg(int x,int y){
    if(!x||!y)return x|y;
    if(rnd[x]<rnd[y]){
        rs[x]=mg(rs[x],y);
        pu(x);return x;
    }
    else{
        ls[y]=mg(x,ls[y]);
        pu(y);return y;
    }
}
il int get(int x){
    while(f[x])x=f[x];
    return x;
}
il int rnk(int x){
    int cnt=sz[ls[x]]+1;
    while(x){
        if(rs[f[x]]==x)cnt+=sz[ls[f[x]]]+1;
        x=f[x];
    }
    return cnt;
}
int main(){
    in(n,q);
    for(int i=1;i<=n;++i)in(v[i]),s[i]=v[i],rnd[i]=rand(),sz[i]=1;
    char opt;int x,y,z;
    while(q--){
        in(opt,x);
        if(opt=='M'){
            in(y),x=get(x),y=get(y);
            if(x!=y)mg(y,x);
        }
        else if(opt=='D'){
            int rt=get(x),rk=rnk(x);
            sl(x,y,rt,rk-1);
            f[x]=f[y]=0;
        }
        else if(opt=='Q'){
            in(y);
            int rt=get(x);
            if(get(y)!=rt){out("-1\n");continue;}
            else{
                int rkx=rnk(x),rky=rnk(y);
                if(rkx>rky)rkx^=rky,rky^=rkx,rkx^=rky;
                sl(x,z,rt,rky);
                sl(x,y,x,rkx-1);
                out(s[y],ln);
                mg(mg(x,y),z);
            }
        }
    }
    flush();
}

splay做法

做法详见注释

#include<bits/stdc++.h>
#pragma GCC optimize(3)
#define il __inline__ __attribute__ ((always_inline))
typedef long long ll;
namespace IO{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;il char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}il void in(char &ch){if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)__=1;else ch=c;}il void in(char *ch){*ch='\0';if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF){__=1;return;}*ch=c;ch++;while((c=gc())!=EOF&&!isspace(c))*ch=c,ch++;if(c==EOF)__=1;*ch='\0';}template<typename T>il void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>il void in(T &x,arr & ... y){in(x),in(y...);}const char ln='\n';static char out_buf[str],*out_s=out_buf,*out_t=out_buf+str;il void flush(){fwrite(out_buf,1,out_s-out_buf,stdout);out_s=out_buf;}il void pt(char c){(out_s==out_t)?(fwrite(out_s=out_buf,1,str,stdout),*out_s++=c):(*out_s++=c);}il void out(const char* s){while(*s)pt(*s++);}il void out(char* s){while(*s)pt(*s++);}il void out(char c){pt(c);}template<typename T>il void out(T x){if(!x){pt('0');return;}if(x<0)pt('-'),x=-x;char a[50],t=0;while(x)a[t++]=x%10,x/= 10;while(t--)pt(a[t]+'0');}template<typename T,typename ... arr>il void out(T x,arr & ... y){out(x),out(y...);}}using namespace IO;
const int N=200001;
int n,q,c[2][N],f[N],v[N];
ll s[N];
#define ls(x) c[0][x]
#define rs(x) c[1][x]
il void pu(int x){s[x]=s[ls(x)]+s[rs(x)]+v[x];}
il int g(int x){return rs(f[x])==x;}
il void rotate(int x){
    int y=f[x],z=f[y],l=g(x),r=!l,w=c[r][x];
    if(z)c[g(y)][z]=x;
    c[r][x]=y,c[l][y]=w;
    if(w)f[w]=y;
    f[x]=z,f[y]=x;
    pu(y),pu(x);
}
il void splay(int x){
    //for(int y;y=f[x];rotate(x))if(f[y])
    //    rotate(g(x)^g(y)?x:y);
    while(f[x])rotate(x);//这题单旋更快
}
il void mg(int x,int y){
    if(x==y)return;
    splay(x),splay(y);
    if(f[x])return;
    //将x接到y子树中最右端
    while(rs(y))y=rs(y);
    f[rs(y)=x]=y;
    pu(y);
}
il void cut(int x){splay(x),f[ls(x)]=0,ls(x)=0,pu(x);}//断开x与x前面的
il ll ask(int x,int y){
    if(x==y)return v[x];
    ll l,r;
    splay(x),l=s[ls(x)];
    splay(y),r=s[ls(y)];
    if(!f[x])return -1;
    //有可能出现端点前后颠倒的情况
    if(l>r)return l-r+v[x];
    else return r-l+v[y];
}
int main(){
    in(n,q);
    for(int i=1;i<=n;++i)in(v[i]);
    char opt;int x,y,z;
    while(q--){
        in(opt,x);
        if(opt=='M')in(y),mg(x,y);
        else if(opt=='D')cut(x);
        else if(opt=='Q')in(y),out(ask(x,y),ln);
    }
    flush();
}
#include<bits/stdc++.h>
#pragma GCC optimize(3)
#define il __inline__ __attribute__ ((always_inline))
typedef long long ll;
namespace IO{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;il char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}il void in(char &ch){if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)__=1;else ch=c;}il void in(char *ch){*ch='\0';if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF){__=1;return;}*ch=c;ch++;while((c=gc())!=EOF&&!isspace(c))*ch=c,ch++;if(c==EOF)__=1;*ch='\0';}template<typename T>il void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>il void in(T &x,arr & ... y){in(x),in(y...);}const char ln='\n';static char out_buf[str],*out_s=out_buf,*out_t=out_buf+str;il void flush(){fwrite(out_buf,1,out_s-out_buf,stdout);out_s=out_buf;}il void pt(char c){(out_s==out_t)?(fwrite(out_s=out_buf,1,str,stdout),*out_s++=c):(*out_s++=c);}il void out(const char* s){while(*s)pt(*s++);}il void out(char* s){while(*s)pt(*s++);}il void out(char c){pt(c);}template<typename T>il void out(T x){if(!x){pt('0');return;}if(x<0)pt('-'),x=-x;char a[50],t=0;while(x)a[t++]=x%10,x/= 10;while(t--)pt(a[t]+'0');}template<typename T,typename ... arr>il void out(T x,arr & ... y){out(x),out(y...);}}using namespace IO;
const int N=200001;
int n,q,c[2][N],f[N],v[N];
ll s[N];
#define ls(x) c[0][x]
#define rs(x) c[1][x]
il void pu(int x){s[x]=s[ls(x)]+s[rs(x)]+v[x];}
il int g(int x){return rs(f[x])==x;}
il void rotate(int x){
    int y=f[x],z=f[y],l=g(x),r=!l,w=c[r][x];
    if(z)c[g(y)][z]=x;
    c[r][x]=y,c[l][y]=w;
    if(w)f[w]=y;
    f[x]=z,f[y]=x;
    pu(y),pu(x);
}
il void splay(int x){
    // for(int y;y=f[x];rotate(x))if(f[y])
        // rotate(g(x)^g(y)?x:y);
    while(f[x])rotate(x);
}
il void mg(int x,int y){
    if(x==y)return;
    splay(x),splay(y);
    if(f[x])return;
    while(rs(y))y=rs(y);
    f[rs(y)=x]=y;
    pu(y);
}
il void cut(int x){splay(x),f[ls(x)]=0,ls(x)=0,pu(x);}
il ll ask(int x,int y){
    if(x==y)return v[x];
    ll l,r;
    splay(x),l=s[ls(x)];
    splay(y),r=s[ls(y)];
    if(!f[x])return -1;
    if(l>r)return l-r+v[x];
    else return r-l+v[y];
}
int main(){
    in(n,q);
    for(int i=1;i<=n;++i)in(v[i]);
    char opt;int x,y,z;
    while(q--){
        in(opt,x);
        if(opt=='M')in(y),mg(x,y);
        else if(opt=='D')cut(x);
        else if(opt=='Q')in(y),out(ask(x,y),ln);
    }
    flush();
}
LG 4847 银河英雄传说V2
comment评论
Search
search