#include<bits/stdc++.h> using namespace std; #define maxn 200000 int read() { char ch=getchar();int f=1,w=0; while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){w=w*10+ch-'0';ch=getchar();} return f*w; } int n,root,m,tot; struct sj { int ch[2]; //左儿子和右儿子 int ff,v; //ff是父亲 v int size; //size是儿子节点个数 int mark; //打上的标记 void init(int x,int fa) //初始化一个节点 左儿子和右儿子以及父亲都清零 { ff=ch[0]=ch[1]=0; size=1;v=x;ff=fa; //含有子节点个数为1 父亲节点为参数fa } }t[maxn]; inline void pushup(int x) { t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+1; } inline void pushdown(int x) { if(t[x].mark) { t[t[x].ch[0]].mark^=1; t[t[x].ch[1]].mark^=1; t[x].mark=0; swap(t[x].ch[0],t[x].ch[1]); } } inline void rotate(int x) //旋转函数 { int y=t[x].ff; int z=t[y].ff; //这是爷爷节点 int k=t[y].ch[1]==x; //看x是左儿子还是右儿子 k取0,1 t[z].ch[t[z].ch[1]==y]=x; //这是把爷爷节点的左/右儿子变成x t[x].ff=z; t[y].ch[k]=t[x].ch[k^1]; t[t[x].ch[k^1]].ff=y; t[x].ch[k^1]=y; t[y].ff=x; //此段画图理解 pushup(y);pushup(x); //再继续进行修改 push_up(); } inline void splay(int x,int goal) { while(t[x].ff!=goal) //当我的这个节点还没有达到目标位置 { int y=t[x].ff;int z=t[y].ff; if(z!=goal) //如果还没有跳到目标节点 继续旋转 (t[z].ch[1]==y)^(t[y].ch[1]==x)?rotate(x):rotate(y); //Warning:: !!!!同边现象时要先翻爸爸再翻儿子 否则不满足搜索树的性质!!!! rotate(x); } if(goal==0)root=x; //如果目标节点是0 那么就把root 根节点变成x } inline void insert(int x) { int u=root,ff=0; //从根节点开始插入 一开始父亲变成0 while(t[u].size!=0)ff=u,u=t[u].ch[x>t[u].v]; //有根的时候 ff父亲变成根节点 u再继续下去向下操作 u=++tot; //tot是实时增加的一个记录子节点个数的全局变量 if(ff)t[ff].ch[x>t[ff].v]=u; //如果父亲不为零 他的父亲的左/右儿子就是u t[u].init(x,ff); //初始化这个节点 并且它的父亲就是ff splay(u,0); //把这个点旋转到根节点 } inline int get_k(int k) { int u=root; while(1) { pushdown(u); if(t[t[u].ch[0]].size>=k)u=t[u].ch[0]; else if(t[t[u].ch[0]].size+1==k)return u; else k-=t[t[u].ch[0]].size+1,u=t[u].ch[1]; } } void write(int u) { pushdown(u); //最后输出之前先push_down一遍 if(t[u].ch[0])write(t[u].ch[0]); //先读左儿子 if(t[u].v>1&&t[u].v<n+2)printf("%d ",t[u].v-1); if(t[u].ch[1])write(t[u].ch[1]); } inline void work(int l,int r) //工作函数 { l=get_k(l); r=get_k(r+2); splay(l,0); splay(r,l); t[t[t[root].ch[1]].ch[0]].mark^=1; } int main() { n=read();m=read(); //n个点 m次翻转 for(int i=1;i<=n+2;++i)insert(i); //跳过建树 直接插入即可 再继续看insert() for(int i=1;i<=m;i++) { int l=read(),r=read(); work(l,r); //工作函数 } write(root); //输出; return 0; //大工告吉 }