# 2. 题解

Splay 的题解戳我=￣ω￣=

#include <bits/stdc++.h>
#define NS (100005)
#define MKP make_pair
#define FIR first
#define SEC second
using namespace std;
typedef pair<int,int> PII;
template<typename _Tp>inline void IN(_Tp&dig)
{
char c;dig=0;
while(c=getchar(),!isdigit(c));
while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
struct N{int l,r,d,v,rev,sz;}e[NS];
int n,m,root,sz;
void pup(int a){e[a].sz=e[e[a].l].sz+e[e[a].r].sz+1;}
void pdown(int a)
{
if(!e[a].rev)return;
int l=e[a].l,r=e[a].r;
if(l)e[l].rev^=1,swap(e[l].l,e[l].r);
if(r)e[r].rev^=1,swap(e[r].l,e[r].r);
e[a].rev=0;
}
int merge(int a,int b)
{
if(!a)return b;if(!b)return a;
pdown(a),pdown(b);
if(e[a].v<e[b].v){e[a].r=merge(e[a].r,b),pup(a);return a;}
e[b].l=merge(a,e[b].l),pup(b);return b;
}
PII split(int a,int d)
{
if(!a)return MKP(0,0);
pdown(a);
int l=e[a].l,r=e[a].r;
if(e[l].sz==d){e[a].l=0,pup(a);return MKP(l,a);}
if(e[l].sz+1==d){e[a].r=0,pup(a);return MKP(a,r);}
if(e[l].sz>d)
{
PII tmp=split(l,d);
e[a].l=tmp.SEC,pup(a);
return MKP(tmp.FIR,a);
}
PII tmp=split(r,d-e[l].sz-1);
e[a].r=tmp.FIR,pup(a);
return MKP(a,tmp.SEC);
}
int build(int l,int r)
{
if(l==r){sz++,e[sz].d=l,e[sz].v=rand(),e[sz].sz=1;return sz;}
int mid=(l+r)>>1;
return merge(build(l,mid),build(mid+1,r));
}
void Print(int a)
{
if(!a)return;
pdown(a),Print(e[a].l),printf("%d ",e[a].d),Print(e[a].r);
}
int main()
{
IN(n),IN(m),srand(n),root=build(1,n);
for(int i=1,a,b;i<=m;i++)
{
IN(a),IN(b);
PII t2=split(root,b),t1=split(t2.FIR,a-1);
e[t1.SEC].rev^=1,swap(e[t1.SEC].l,e[t1.SEC].r);
root=merge(t1.FIR,merge(t1.SEC,t2.SEC));
}
Print(root);
return 0;
}