用splay来维护序列

#include <iostream>
#include <cstdio>

using namespace std;

struct Node
    {
        Node *ch[2];
        int v,s;

        bool flip;
        Node(){};
        Node(int v,Node* o):v(v)
            {s=v+1;ch[0]=ch[1]=o;}
        int cmp(int x) const{
            int l_size=ch[0]->s+1;
            if(x==l_size)return(-1);
            return (x<l_size)?(0):(1);
        }
        void maintain()
            {s=ch[0]->s+ch[1]->s+1;}
        void pushdown(){
            if(flip){
                flip=0;
                swap(ch[0],ch[1]);
                ch[0]->flip^=1;
                ch[1]->flip^=1;
            }
        }
    };
struct SplayTree
{
    Node *root,*null;
    SplayTree(){
        null=new Node;
        null->ch[0]=null->ch[1]=null;
        null->v=null->s=null->flip=0;
        root=null;
    }
    ~SplayTree(){
        clear(root);
        delete null;
    }
    void build(Node* &o,int n){
        //n=0既为最左边的虚拟节点
        if(n>=0){
            o=new Node(n,null);
            build(o->ch[0],n-1);
        }
    }
    void rotate(Node* &o,int d){
        Node* k=o->ch[d^1];
        o->ch[d^1]=k->ch[d];
        k->ch[d]=o;
        o->maintain();
        k->maintain();
        o=k;
    }

    void splay(Node* &o,int k){
        o->pushdown();
        int d=o->cmp(k);
        if(d==1) k-=o->ch[0]->s+1;
        if(d!=-1){
            Node* p=o->ch[d];
            p->pushdown();
            int d2=p->cmp(k);
            int k2=(d2==0 ? k : k-p->ch[0]->s-1);
            if(d2!=-1){
                splay(p->ch[d2],k2);
                if(d==d2)
                    rotate(o,d^1);
                else
                    rotate(o->ch[d],d);
            }
            rotate(o,d^1);
        }
        //cout<<(o->v)<<"("<<(o->ch[0]->v)<<","<<(o->ch[1]->v)<<")"<<endl;
    }
    Node* merge(Node* left,Node* right){
    //left should not be NULL
        splay(left,left->s);
        left->ch[1]=right;
        left->maintain();
        return left;
    }
    void split(Node* o,int k,Node* &left,Node* &right){
        splay(o,k);
        left=o;
        right=o->ch[1];
        o->ch[1]=null;
        left->maintain();
    }
    void clear(Node* &o)
    {
        if(o->ch[0]!=null)  clear(o->ch[0]);
        if(o->ch[1]!=null)  clear(o->ch[1]);
        delete o;
        o=null;
    }
    void print(Node* o)
    {
        if(o==null)return;
        o->pushdown();
        print(o->ch[0]);
        if(o->v>0)
            printf("%d\n",o->v);
        print(o->ch[1]);
    }
    void process(int a,int b){
        //a的名次是a+1 a-1的名次是a
        //左边序列到名次a
        Node *lef,*rig,*mid,*t;
        split(root,a,lef,t);
        split(t,b-a+1,mid,rig);
        mid->flip^=1;
        root=merge(merge(lef,rig),mid);
    }
};

int main()
{
    int n,m,a,b;
    scanf("%d%d",&n,&m);
    SplayTree s;
    s.build(s.root,n);
    for(int i=0;i<m;++i){
        scanf("%d%d",&a,&b);
        s.process(a,b);
    }
    s.print(s.root);
    return 0;
}