题目大意

您需要写一种数据结构，来维护一个有$n$个数的有序数列，其中需要提供以下$m$次操作：翻转区间

例如原有序序列是$“5 4 3 2 1”$，翻转区间是$[2,4]$的话，结果是$“5 2 3 4 1”$

数据范围

$n,m\leqslant 100000$

题解

splay区间翻转

注意弄多两个边界节点，防止出现各种各样的小问题，具体怎么做看代码吧！

程序

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define inf 0x3f3f3f3f
#define maxn 105000
using namespace std;

int t[maxn][2],f[maxn],size[maxn],rev[maxn];
int n,m,rt;
inline void pushup(int x){size[x]=size[t[x][0]]+size[t[x][1]]+1;}
inline void pushdown(int x){if (rev[x]){swap(t[x][0],t[x][1]);rev[x]^=1;rev[t[x][1]]^=1;rev[t[x][0]]^=1;}}
inline void rotate(int x,int &k){
    int y=f[x],z=f[y],l,r;
    if (t[y][0]==x) l=0;else l=1;r=l^1;
    if (y==k) k=x;
    else {if (t[z][0]==y) t[z][0]=x;else t[z][1]=x;}
    f[x]=z;f[y]=x;f[t[x][r]]=y;
    t[y][l]=t[x][r];t[x][r]=y;
    pushup(y);pushup(x);
}
inline void splay(int x,int &k){
    while(x!=k){
        int y=f[x],z=f[y];
        if (y!=k){
            if ((t[y][0]==x)^(t[z][0]==y)) rotate(x,k);
            else rotate(y,k);
        }
        rotate(x,k);
    }
}

void build(int l,int r,int last){
    if (l>r) return;
    if (l==r){
        f[l]=last;size[l]=1;
        if (l<last) t[last][0]=l;
        else t[last][1]=l;
    }
    int mid=(l+r)>>1;
    build(l,mid-1,mid);build(mid+1,r,mid);
    f[mid]=last;pushup(mid);
    if (mid<last) t[last][0]=mid;
    else t[last][1]=mid;
}
int findsum(int x,int rank){
    pushdown(x);
    if(size[t[x][0]]+1==rank) return x;
    else if(size[t[x][0]]>=rank)return findsum(t[x][0],rank);
    else return findsum(t[x][1],rank-size[t[x][0]]-1);
}    
inline void rever(int l,int r){
    int x=findsum(rt,l),y=findsum(rt,r+2);
    splay(x,rt);splay(y,t[x][1]);
    rev[t[y][0]]^=1;
}
int main(){
    scanf("%d%d",&n,&m);
    build(1,n+2,0);rt=(n+3)>>1;
    For(i,1,m){
        int a,b;
        scanf("%d%d",&a,&b);
        rever(a,b);
    }
    For(i,2,n+1) printf("%d ",findsum(rt,i)-1);
    puts("");
    return 0;
}