注意下传翻转标记，还有在bzoj上不能输出换行符。
#include<bits/stdc++.h>
using namespace std;
struct one
{
int fa,rec,sum,ch[2],v,tg;
};
one tree[1000000];
int l,r,n,m,tot=0,sum=0;
bool f[500000];
#define root tree[0].ch[1]
void maketree(int l,int r)
{
int mid=(l+r)>>1;
tree[++tot].v=mid;
f[mid]=true;
tree[tot].rec=1;
int now=tot;
if(l==mid)
{
if(r==mid||f[r]){tree[tot].sum=1;return;}
tree[tot].sum=2;
tree[tot].ch[1]=tot+1;
tot++;
tree[tot].rec=1;tree[tot].sum=1;
tree[tot].v=r;
tree[tot].fa=tot-1;
return;
}
if(!f[(l+mid)/2])
{
tree[tot+1].fa=now;
tree[now].ch[0]=tot+1;
maketree(l,mid);
}
if(!f[(mid+r+1)/2])
{
tree[tot+1].fa=now;
tree[now].ch[1]=tot+1;
maketree(mid+1,r);
}
tree[now].sum=tree[tree[now].ch[0]].sum+tree[tree[now].ch[1]].sum+1;
}
inline void worktg(int x)
{
if(tree[x].tg)
{
swap(tree[x].ch[0],tree[x].ch[1]);
tree[tree[x].ch[0]].tg^=1;
tree[tree[x].ch[1]].tg^=1;
tree[x].tg=0;
}
}
inline int arank(int x)
{
int now=root;
while(1)
{
worktg(now);
int used=tree[now].sum-tree[tree[now].ch[1]].sum;
if(x<=used&&x>tree[tree[now].ch[0]].sum)break;
if(x<used)now=tree[now].ch[0];
else x-=used,now=tree[now].ch[1];
}
return now;
}
inline int iden(int x)
{
return tree[tree[x].fa].ch[0]==x?0:1;
}
inline void connect(int x,int fa,int how)
{
tree[x].fa=fa;
tree[fa].ch[how]=x;
}
inline void update(int x)
{
tree[x].sum=tree[tree[x].ch[0]].sum+tree[tree[x].ch[1]].sum+1;
}
inline void rotate(int x)
{
int Y=tree[x].fa;
int R=tree[Y].fa;
int Yson=iden(x);
int Rson=iden(Y);
int B=tree[x].ch[Yson^1];
connect(x,R,Rson);
connect(Y,x,Yson^1);
connect(B,Y,Yson);
update(Y);update(x);
}
void splay(int x,int to)
{
to=tree[to].fa;
while(tree[x].fa!=to)
{
if(tree[tree[x].fa].fa==to)rotate(x);
else if(iden(x)==iden(tree[x].fa))rotate(tree[x].fa),rotate(x);
else rotate(x),rotate(x);
}
}
void dfs(int p)
{
if(!p)return;
worktg(p);
dfs(tree[p].ch[0]);
sum++;
if(sum!=n)printf("%d ",tree[p].v);
else printf("%d",tree[p].v);
dfs(tree[p].ch[1]);
}
int main()
{
//freopen("xf.in","r",stdin);
scanf("%d%d",&n,&m);
maketree(1,n);
tree[1].fa=0;
tree[0].ch[1]=1;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&l,&r);
l--,r++;
if(l==0&&r==n+1)
{
tree[root].tg^=1;
}
else if(l==0)
{
int p=arank(r);
splay(p,root);
tree[tree[root].ch[0]].tg^=1;
}
else if(r==n+1)
{
int p=arank(l);
splay(p,root);
tree[tree[root].ch[1]].tg^=1;
}
else
{
int p=arank(l);
splay(p,root);
p=arank(r);
splay(p,tree[root].ch[1]);
tree[tree[tree[root].ch[1]].ch[0]].tg^=1;
}
}
dfs(root);
return 0;
}