P3391 【模板】文艺平衡树

给定一个序列，经过若干次 [ l , r ] 区间的旋转，问m 次之后序列。

考虑splay 旋转，维护一个键值，那么点树上的位置，即中序遍历，实际上反映了它在序列的位置。

把一个splay中序遍历，实际上得到了一个序列，那么如何将区间旋转？

把 l -1 旋转到根，r + 1旋转到根右儿子，那么红色的子树实际上就是 [ l , r ] 的区间，旋转实际上把每一个点左右儿子互换即可。

采用标记法，翻转时只是标记，不深入。

注意：BST的中序遍历实际上是原序列，那么将区间翻转，实际上是将左右子树翻转。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int ch[N][2];
int size[N],pre[N],rev[N];
int root;
void pushup(int u){
    size[u]=size[ch[u][0]]+size[ch[u][1]]+1;
}
void pushdown(int u){//tag下放
    if(rev[u]){
        int &ls=ch[u][0],&rs=ch[u][1];
        swap(ls,rs);
        rev[ls]^=1;rev[rs]^=1;rev[u]=0;
    }
}
void rotate(int x,int &k){//x向k方向旋转
    int y=pre[x],z=pre[y],kind;
    if(ch[y][0]==x)kind=1;else kind=0;
    if(y==k)k=x;
    else {if(ch[z][0]==y)ch[z][0]=x;else ch[z][1]=x;}
    ch[y][kind^1]=ch[x][kind];pre[ch[y][kind^1]]=y;
    ch[x][kind]=y;pre[y]=x;pre[x]=z;
    pushup(x);pushup(y);
}
void splay(int x,int &k){//将x旋转到k
    while(x!=k){
        int y=pre[x],z=pre[y];
        if(y!=k){
            if((ch[y][0]==x)^(ch[z][0]==y))rotate(x,k);//之字形旋转
            else rotate(y,k);//直线型旋转
        }
        rotate(x,k);
    }
}
void build(int l,int r,int x){
    if(l>r)return ;
    int mid=(l+r)/2;
    if(mid<x)ch[x][0]=mid;else ch[x][1]=mid;
    pre[mid]=x;size[mid]=1;
    if(l==r)return ;
    build(l,mid-1,mid);build(mid+1,r,mid);
    pushup(mid);
}
int find(int x,int k){//查找下标为k的点
    pushdown(x);int s=size[ch[x][0]];
    if(k==s+1)return x;
    if(k<=s)return find(ch[x][0],k);
    else return find(ch[x][1],k-s-1);
}
void rever(int l,int r){
    int x=find(root,l),y=find(root,r+2);
    splay(x,root);splay(y,ch[x][1]);int z=ch[y][0];
    rev[z]^=1;
}
int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    root=(n+3)/2;build(1,n+2,root);
    for(int i=1,l,r;i<=m;i++){
        scanf("%d %d",&l,&r);
        rever(l,r);
    }   
    for(int i=2;i<=n+1;i++){
        printf("%d ",find(root,i)-1);
    }
    // system("pause");
    return 0;
}

View Code