求调，带父指针splay大红大紫，写法类似OIwiki

RT，带父的指针 splay，RE 了，而且 luogu 的样例 WA 但我们学校的水样例过了。

随手打了个随机数跑了五六次操作就挂了，也是 RE。数据我忘了存，不过很好构造。我当时以为 114514 的长度 +17 个随机区间不能造出来，然后惊奇地发现 RE 了。

有两个 splay，一个是 OIwiki 上那种直接旋到根的，另一个是自己写的，仿照 OIwiki 的做法旋到指定节点。其他部分过了平衡树板子题，大概率就是自己写的这个 splay 挂了。

代码（不要嫌弃马蜂QAQ）：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//static char buf[1000000],*p1=buf,*p2=buf,obuf[1000000],*p3=obuf;
//#define flush() fwrite(obuf,p3-obuf,1,stdout)
//#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
//#define putchar(x) (p3-obuf<1000000)?(*p3++=x):(flush(),p3=obuf,*p3++=x)
template<typename T> inline void read(T&);
template<typename T> inline void write(T);
template<typename... Args> inline void read(Args& ...);
template<typename... Args> inline void write(Args ...);
inline void read(char*);
inline void read(char&);
inline void read(string&);
inline void write(char);
inline void write(char*);
inline void write(const char*);
int n,m;
template<typename T=int> class Splay{
private:
    struct node{
        bool tag;
        T val;
        int cnt,siz;
        node* fa;
        node* ch[2];
        node():tag(0),val(),cnt(0),siz(0),fa(nullptr){ch[0]=ch[1]=nullptr;}
        node(T Val):tag(0),val(Val),cnt(1),siz(1),fa(nullptr){ch[0]=ch[1]=nullptr;}
        node(T Val,node* Fa):tag(0),val(Val),cnt(1),siz(1),fa(Fa){ch[0]=ch[1]=nullptr;}
    };
    int get_siz(node* p){return p==nullptr?0:p->siz;}
    int get_cnt(node* p){return p==nullptr?0:p->cnt;}
    T get_val(node* p){return p==nullptr?0:p->val;}
    node* root;
    void updata(node* p){if(p) p->siz=get_siz(p->ch[0])+get_siz(p->ch[1])+get_cnt(p);}
    void push_down(node* p){
        if((!p)||(!(p->tag))) return;
        if(p->ch[0]) (p->ch[0])->tag^=1;
        if(p->ch[1]) (p->ch[1])->tag^=1;
        swap(p->ch[0],p->ch[1]);
        p->tag=0;
    }
    bool check(node* p){return p==(p->fa)->ch[1];}
    void clear(node* p){
        if(p) delete p;
        p=nullptr;
    }
    void rotate(node* p){
        node *fa=p->fa,*gra=fa->fa;
        bool chk=check(p);
        push_down(p),push_down(fa);
        fa->ch[chk]=p->ch[chk^1];
        if(p->ch[chk^1]) (p->ch[chk^1])->fa=fa;
        p->ch[chk^1]=fa,fa->fa=p,p->fa=gra;
        if(gra) gra->ch[fa==(gra->ch[1])]=p;
        updata(p),updata(fa);
    }
    node* kth(int rnk){
        node* p=root;
        while(1){
            push_down(p);
            if(p->ch[0]&&rnk<=get_siz(p->ch[0])) p=p->ch[0];
            else{
                rnk-=get_cnt(p)+get_siz(p->ch[0]);
                if(rnk<=0) return splay(p),p;
                else p=p->ch[1];
            }
        }
    }
public:
    Splay():root(nullptr){}
    node* pre(){
        node* p=root->ch[0];
        if(!p) return p;
        while(p->ch[1]) p=p->ch[1];
        return splay(p),p;
    }
    node* nxt(){
        node* p=root->ch[1];
        if(!p) return p;
        while(p->ch[0]) p=p->ch[0];
        return splay(p),p;
    }
//  void splay(node* p,node* rt){
//      for(node* fa=p->fa;(fa=p->fa)==rt;rotate(p)) if(fa->fa) rotate(check(p)==check(fa)?fa:p);
////        root=p;
//  }
    void splay(node* p,node* rt){
//      out();
//      printf("%p %p %p\n",p->fa,rt->ch[0],rt->ch[1]);
        node* q=p->fa;
//      if(q) printf("%p %p\n",q->fa,rt);
        for(node* fa=p->fa;(fa=p->fa)&&fa!=rt->fa;rotate(p)) if(fa->fa!=rt->fa) /*cout<<"zhouji\n",*/rotate(check(p)==check(fa)?fa:p);
        if(rt==root) root=p;
    }
    void splay(node* p){
        push_down(p);
        for(node* fa=p->fa;(fa=p->fa);rotate(p)){
            if(fa->fa) rotate(check(p)==check(fa)?fa:p);
        }
        root=p;
    }
    void insert(T val){
        if(!root){
            root=new node(val);
            updata(root);
            return;
        }
        node *p=root,*fa=nullptr;
        while(1){
            if(p->val==val){
                p->cnt++;
                updata(p),updata(fa);
                splay(p);
                break;
            }
            fa=p;
            p=p->ch[p->val<val];
            if(!p){
                p=new node(val,fa);
                fa->ch[fa->val<val]=p;
                updata(p),updata(fa);
                splay(p);
                break;
            }
        }
    }
    void erase(T val){
        get_rank(val);
        if(get_cnt(root)>1){
            root->cnt--;
            updata(root);
            return;
        }
        if(!root->ch[0]&&!root->ch[1]){
            clear(root);
            root=nullptr;
            return;
        }
        if(!root->ch[0]){
            node* p=root;
            root=root->ch[1],root->fa=nullptr;
            clear(p);
            return;
        }
        if(!root->ch[1]){
            node* p=root;
            root=root->ch[0],root->fa=nullptr;
            clear(p);
            return;
        }
        node *p=root,*pr=pre();
        (p->ch[1])->fa=pr;
        pr->ch[1]=p->ch[1];
        clear(p),updata(root);
    }
    int get_rank(T val){
        int ret=0;
        node* p=root;
        while(1){
            if(val<p->val) p=p->ch[0];
            else{
                ret+=get_siz(p->ch[0]);
                if(val==p->val) return splay(p),ret+1;
                else ret+=get_cnt(p),p=p->ch[1];
            }
        }
    }
    T k_th(int rnk){
        node* p=root;
        while(1){
            push_down(p);
            if(p->ch[0]&&rnk<=get_siz(p->ch[0])) p=p->ch[0];
            else{
                rnk-=get_cnt(p)+get_siz(p->ch[0]);
                if(rnk<=0) return splay(p),p->val;
                else p=p->ch[1];
            }
        }
    }
    T get_pre(T val){
        insert(val);
        T ret=get_val(pre());
        erase(val);
        return ret;
    }
    T get_nxt(T val){
        insert(val);
        T ret=get_val(nxt());
        erase(val);
        return ret;
    }
    void reverse(int L,int R){
        node *l=kth(L),*r=kth(R+1);
//      write(l->val,' ',r->val,'\n');
        splay(r);
        splay(l);
//      out();
//      cout<<endl;
//      write("zhouji\n");
//      splay(r,root->ch[1]);
        node *p=(root->ch[1]);
//      out();
//      printf("%d %p\n",p->val,p);
        p=p->ch[0];
//      printf("%p\n",p);
//      printf("%d\n",root->val);
        p->tag^=1;
//      write("zhouya\n");
//      printf("%d\n",root->val);
    }
    void print(node* p){
        if(!p) return;
        push_down(p);
        print(p->ch[0]);
        if((p->val)>=1&&(p->val)<=n) write((p->val),' ');
        print(p->ch[1]);
    }
    void print(){print(root);}
    void out(node* p){
        if(!p) return;
        cout<<(p->val)<<":"<<"("<<((p->ch[0])?(p->ch[0])->val:-1)<<","<<((p->ch[1])?(p->ch[1])->val:-1)<<")\n";
        out(p->ch[0]),out(p->ch[1]);
    }
    void out(){out(root);}
};
Splay<int> tr;
signed main(){
//  freopen("2.txt","r",stdin);
    read(n,m);
    tr.insert(0),tr.insert(n+1);
    for(int i=1;i<=n;i++) tr.insert(i);
    for(int l,r;m--;) read(l,r)/*,cout<<l<<" "<<r<<"\n"*/,tr.reverse(l,r+1);//,tr.print(),cout<<endl;
    tr.print();
//  flush();
    return 0; 
}

template<typename T> inline void read(T& x){
    x=0;bool flag=0;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') flag=1;
    if(flag) for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)-(ch&15);
    else for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch&15);
}
template<typename T> inline void write(T x){
    static int sta[40];
    int top=0;
    if(x<0){
        putchar('-');
        do sta[top++]=(-x)%10,x/=10;
        while(x);
    }
    else{
        do sta[top++]=x%10,x/=10;
        while(x);
    }
    while(top) putchar(sta[--top]^48);
}
inline void write(char x){putchar(x);}
inline void read(char& c){while((c=getchar())==' '||c=='\n');}
inline void read(string& str){
    char ch;
    str="";
    while((ch=getchar())==' '||ch=='\n');
    str+=ch;
    while((ch=getchar())!=' '&&ch!='\n') str+=ch;
}
inline void read(char* str){
    while((*str=getchar())==' '||*str=='\n');
    while((*++str=getchar())!=' '&&*str!='\n');
    *str=0;
}
inline void write(char* str){while(*str!='\0') putchar(*str++);}
inline void write(const char* str){while(*str!='\0') putchar(*str++);}
template<typename... Args> inline void read(Args& ...args){(void)initializer_list<int>{(read(args),0)...};}
template<typename... Args> inline void write(Args ...args){(void)initializer_list<int>{(write(args),0)...};}