fhq_treap || BZOJ 3223: Tyvj 1729 文艺平衡树 || Luogu P3391 【模板】文艺平衡树（Splay）...

蔚落 2021-10-25 14:32 245阅读 0赞

题面： [【模板】文艺平衡树（Splay）][Splay]

题解：无

代码：

1 #include<cstdio>
     2 #include<cstring>
     3 #include<iostream>
     4 #include<cstdlib>
     5 using namespace std;
     6 inline int rd(){
     7     int x=0,f=1;char c=getchar();
     8     while(c<'0'||c>'9'){
        if(c=='-')f=-1; c=getchar();}
     9     while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}
    10     return f*x;
    11 }
    12 const int maxn=(1e5)+50;
    13 int N,M,tot=0,val[maxn],siz[maxn],pr[maxn],rt=0,chd[maxn][3];
    14 int L,R,x,y,z;
    15 bool fl[maxn];
    16 inline int New_node(int a){
    17     val[++tot]=a;
    18     siz[tot]=1;
    19     pr[tot]=rand();
    20     return tot;
    21 }
    22 inline void Pushup(int a){
    23     siz[a]=siz[chd[a][0]]+siz[chd[a][1]]+1;
    24     return;
    25 }
    26 inline void Pushdown(int a){
    27     if(fl[a]){
    28         swap(chd[a][0],chd[a][1]);
    29         if(chd[a][0])fl[chd[a][0]]^=1;
    30         if(chd[a][1])fl[chd[a][1]]^=1;
    31         fl[a]=0;
    32     }
    33     return;
    34 }
    35 inline int Merge(int a,int b){
    36     if(!a||!b)return (a+b);
    37     if(pr[a]<pr[b]){
    38         Pushdown(a);
    39         chd[a][1]=Merge(chd[a][1],b);
    40         Pushup(a);
    41         return a;
    42     }
    43     else{
    44         Pushdown(b);
    45         chd[b][0]=Merge(a,chd[b][0]);
    46         Pushup(b);
    47         return b;
    48     }
    49 }
    50 inline void Split(int now,int k,int &x,int &y){
    51     if(!now){x=y=0; return;}
    52     Pushdown(now);
    53     if(siz[chd[now][0]]+1<=k){
    54         x=now;
    55         Split(chd[now][1],k-siz[chd[now][0]]-1,chd[now][1],y);
    56     }
    57     else {
    58         y=now;
    59         Split(chd[now][0],k,x,chd[now][0]);
    60     }
    61     Pushup(now);
    62     return;
    63 }
    64 inline void Work(int now){
    65     if(!now)return;
    66     Pushdown(now);
    67     Work(chd[now][0]);
    68     printf("%d ",val[now]);
    69     Work(chd[now][1]);
    70     return;
    71 }
    72 int main(){
    73     srand(20030304);
    74     N=rd();M=rd();
    75     for(int i=1;i<=N;i++)rt=Merge(rt,New_node(i));
    76     while(M--){
    77         L=rd();R=rd();
    78         Split(rt,L-1,x,y);
    79         Split(y,R-L+1,y,z);
    80         fl[y]^=1;
    81         rt=Merge(Merge(x,y),z);
    82     }
    83     Work(rt);
    84     return 0;
    85 }

--------------------

By:AlenaNuna

转载于:https://www.cnblogs.com/AlenaNuna/p/10920473.html

[Splay]: https://www.luogu.org/problemnew/show/P3391