给定一个区间和m次操作，每次操作将一段区间翻转，求m次操作后的区间。

链接

LOJ105

题解

Splay复习题

用Splay维护[0,n+2]。假如操作是翻转[a,b]，将a-1转至根，b+1转至右子树，则b+1的左子树即为要维护的区间，用翻转标记处理即可。

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define N 200010
using namespace std;

int n,m,i,x,y,a,b,root;
int f[N],s[N][2],size[N],tag[N];

inline void Swap(int &x,int &y){x^=y^=x^=y;}
inline int Get(int x){return (x==s[f[x]][1]);}

inline void Push(int x){
    Swap(s[x][0],s[x][1]);
    tag[s[x][0]]^=1;    tag[s[x][1]]^=1;
    tag[x]=0;
}

inline void Update(int x){
    size[x]=size[s[x][0]]+size[s[x][1]]+1;
}

inline int Build(int l,int r){
    int mid=(l+r)>>1;
    if (l>r)    return 0;
    s[mid][0]=Build(l,mid-1);
    s[mid][1]=Build(mid+1,r);
    Update(mid);
    f[s[mid][0]]=f[s[mid][1]]=mid;
    return mid;
}

inline void Rotate(int x){
    int fa=f[x],gf=f[fa],o=Get(x),oo=Get(fa);
    f[x]=gf;    f[fa]=x;    f[s[x][o^1]]=fa;
    s[fa][o]=s[x][o^1]; s[x][o^1]=fa;   s[gf][oo]=x;
    Update(fa); Update(x);
}

inline void Splay(int x,int y){
    for (;f[x]!=y;Rotate(x))
        if (f[f[x]]!=y) Rotate((Get(x)==Get(f[x]))?f[x]:x);
    if (!y) root=x;
}

inline int Find(int x){
    int i=root;
    while (1){
        if (tag[i]) Push(i);
        if (x==size[s[i][0]]+1) return i;
        else if (x<=size[s[i][0]])  i=s[i][0];
        else x-=(size[s[i][0]]+1),i=s[i][1];
    }
}

inline void Print(int x){
    if (!x) return;
    if (tag[x]) Push(x);
    Print(s[x][0]);
    if (x!=1&&x!=n+2)   printf("%d ",x-1);
    Print(s[x][1]);
}

int main(){
    scanf("%d%d",&n,&m);
    root=Build(1,n+2);
    while (m--){
        scanf("%d%d",&x,&y);
        a=Find(x);  b=Find(y+2);
        Splay(a,0); Splay(b,a);
        tag[s[s[a][1]][0]]^=1;
    }
    Print(root);
    return 0;
}