splay模版题吧 只有区间翻转

至于为什么要把须翻转区间旋到根 因为查找一个区间可以先找出他左端点左边第一个点和右端点x右边第一个点y 然后将x旋到根节点 y旋到x的右儿子 这样x的右边的点就是所有大于x的点而y的左边是所有小于y的点 这样刚好包涵了所需要翻转的区间

#include
      
       #include
       
        #include
        
         using namespace std;const int M=100005;int n,m,root;int c[M][2],fa[M],size[M];bool rev[M];void pushup(int k){
    int l=c[k][0],r=c[k][1]; size[k]=size[l]+size[r]+1;}void pushdown(int k){    int l=c[k][0],r=c[k][1];    if(rev[k]){        swap(c[k][0],c[k][1]);        rev[l]^=1; rev[r]^=1; rev[k]=0;    }}void build(int l,int r,int f){    if(l>r) return ;    if(l==r){        fa[l]=f; size[l]=1;        if(l
         
          >1;    build(l,mid-1,mid); build(mid+1,r,mid);    fa[mid]=f; pushup(mid);    if(mid
          
           =rank) return find(l,rank);    else return find(r,rank-size[l]-1);}void rever(int l,int r){    int x=find(root,l),y=find(root,r+2);    splay(x,root); splay(y,c[root][1]);    rev[c[y][0]]^=1;}int main(){    scanf("%d %d",&n,&m);    build(1,n+2,0); root=(n+3)>>1;    while(m--){        int l,r; scanf("%d %d",&l,&r);        rever(l,r);    }    for(int i=2;i<=n+1;i++) printf("%d ",find(root,i)-1);    return 0;}