P3391 文藝平衡樹（Splay區間翻轉）

題解：

Splay區間反轉的模闆題。

翻轉[3,5]時，我們可以将3的前驅找到，5的後繼找到，然後根節點的右兒子的左子樹就是屬于[3,5]這個區間的數，可以自己畫畫就容易知道了。

然後就是給這個結點打上标記表示這個區間是需要翻轉的，在以後查詢或者需要時就标記下放，左右子樹翻轉即可。

AC代碼：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1e5+10;
const int MOD = 998244353;
struct node{
    int son[2],fa,val,sz,lazy;
    void init(int f,int v){ fa=f; val=v; sz=1; }
}t[MAXN];
int root,tot,n,m,a[MAXN];
inline int id(int x){ return x==t[t[x].fa].son[1]; }
inline void pushup(int x){
    t[x].sz = t[t[x].son[0]].sz+t[t[x].son[1]].sz+1;
}
inline void pushdown(int x){
    if(t[x].lazy){
        t[t[x].son[0]].lazy ^= 1;
        t[t[x].son[1]].lazy ^= 1;
        t[x].lazy = 0;
        swap(t[x].son[0],t[x].son[1]);
    }
}
inline void rotate(int x){
    int y=t[x].fa,z=t[y].fa,k=id(x);
    t[z].son[id(y)]=x; t[x].fa=z;
    t[y].son[k]=t[x].son[k^1]; t[t[x].son[k^1]].fa=y;
    t[x].son[k^1]=y; t[y].fa=x;
    pushup(y); pushup(x);
}
inline void splay(int x,int pos){
    while(t[x].fa!=pos){
        int y=t[x].fa,z=t[y].fa;
        if(z!=pos) id(x)==id(y) ? rotate(y):rotate(x);
        rotate(x);
    }
    if(!pos) root=x;
}
inline int build(int rt,int l,int r){
    if(l>r) return 0; int mid=(l+r)>>1;
    int u=++tot;
    t[u].init(rt,a[mid]);
    t[u].son[0]=build(u,l,mid-1);
    t[u].son[1]=build(u,mid+1,r);
    pushup(u); return u;
}
inline int kth(int x){
    int u=root;
    while(1){
        pushdown(u);
        if(t[t[u].son[0]].sz>=x) u=t[u].son[0];
        else{
            x -= t[t[u].son[0]].sz+1;
            if(!x) return u;
            u = t[u].son[1];
        }
    }
}
void dfs(int u){
    pushdown(u);
    if(t[u].son[0]) dfs(t[u].son[0]);
    if(t[u].val>=1 && t[u].val<=n) printf("%d ",t[u].val);
    if(t[u].son[1]) dfs(t[u].son[1]);
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);
#endif // ONLINE_JUDGE
    scanf("%d%d",&n,&m); a[1]=-1e9; a[n+2]=1e9;
    for(int i=2;i<=n+1;i++) a[i]=i-1;
    root = build(0,1,n+2);
    while(m--){
        int l,r; scanf("%d%d",&l,&r);
        int ll=kth(l),rr=kth(r+2);
        splay(ll,0); splay(rr,ll);
        t[t[t[root].son[1]].son[0]].lazy ^= 1;
    }
    dfs(root);
    return 0;
}


           

AC代碼：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1e5+10;
const int MOD = 998244353;
struct node{
    int son[2],fa,val,sz,lazy;
    void init(int f,int v){ fa=f; val=v; sz=1; }
}t[MAXN];
int root,tot,n,m;
inline int id(int x){ return x==t[t[x].fa].son[1]; }
inline void pushup(int x){
    t[x].sz = t[t[x].son[0]].sz+t[t[x].son[1]].sz+1;
}
inline void pushdown(int x){
    if(t[x].lazy){
        t[t[x].son[0]].lazy ^= 1;
        t[t[x].son[1]].lazy ^= 1;
        t[x].lazy = 0;
        swap(t[x].son[0],t[x].son[1]);
    }
}
inline void rotate(int x){
    int y=t[x].fa,z=t[y].fa,k=id(x);
    t[z].son[id(y)]=x; t[x].fa=z;
    t[y].son[k]=t[x].son[k^1]; t[t[x].son[k^1]].fa=y;
    t[x].son[k^1]=y; t[y].fa=x;
    pushup(y); pushup(x);
}
inline void splay(int x,int pos){
    while(t[x].fa!=pos){
        int y=t[x].fa,z=t[y].fa;
        if(z!=pos) id(x)==id(y) ? rotate(y):rotate(x);
        rotate(x);
    }
    if(!pos) root=x;
}
inline void Insert(int x){
    int u=root,fa=0;
    while(u) fa=u,u=t[u].son[x>t[u].val];
    u=++tot;
    if(fa) t[fa].son[x>t[fa].val]=u;
    t[u].init(fa,x);
    splay(u,0);
}
inline int kth(int x){
    int u=root;
    while(1){
        pushdown(u);
        if(t[t[u].son[0]].sz>=x) u=t[u].son[0];
        else{
            x -= t[t[u].son[0]].sz+1;
            if(!x) return u;
            u = t[u].son[1];
        }
    }
}
void dfs(int u){
    pushdown(u);
    if(t[u].son[0]) dfs(t[u].son[0]);
    if(t[u].val>=2 && t[u].val<=n+1) printf("%d ",t[u].val-1);
    if(t[u].son[1]) dfs(t[u].son[1]);
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);
#endif // ONLINE_JUDGE
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n+2;i++) Insert(i);
    while(m--){
        int l,r; scanf("%d%d",&l,&r);
        int ll=kth(l),rr=kth(r+2);
        splay(ll,0); splay(rr,ll);
        t[t[t[root].son[1]].son[0]].lazy ^= 1;
    }
    dfs(root);
    return 0;
}