1 #include<cstdio> 2 const int maxn=3e5; 3 void swap_(int&x,int&y){x^=y,y^=x,x^=y;} 4 int n,m,hd,rt; 5 int t[maxn],f[maxn],sz[maxn],id[maxn],s[maxn][2]; 6 void pushdown(int k){swap_(s[k][0],s[k][1]),t[s[k][0]]^=1,t[s[k][1]]^=1,t[k]=0;} 7 void rot(int&k,int x){ 8     int y=f[x],z=f[y],l,r; 9     l=s[y][0]==x?0:1,r=l^1;10     if(y==k) k=x;11     else{12         if(s[z][0]==y) s[z][0]=x;13         else s[z][1]=x;14     }15     f[x]=z,f[y]=x,f[s[x][r]]=y;16     s[y][l]=s[x][r],s[x][r]=y;17     sz[y]=sz[s[y][0]]+sz[s[y][1]]+1;18     sz[x]=sz[s[x][0]]+sz[s[x][1]]+1;19 }20 void splay(int&k,int x){while(x!=k) rot(k,x);}21 int find(int k,int x){22     if(t[k]) pushdown(k);23     int l=s[k][0],r=s[k][1];24     if(sz[l]+1==x) return k;25     if(sz[l]>=x) return find(l,x);26     else return find(r,x-sz[l]-1);27 }28 void rever(int l,int r){29     int x=find(rt,l),y=find(rt,r+2);30     splay(rt,x),splay(s[x][1],y);31     int z=s[y][0];32     t[z]^=1;33 }34 void build(int l,int r,int fa){35     if(l>r) return;36     int now=id[l],last=id[fa];37     if(l==r){38         f[now]=last,sz[now]=1;39         if(l<fa) s[last][0]=now;40         else s[last][1]=now;41         return;42     }43     int mid=l+r>>1;now=id[mid];44     build(l,mid-1,mid);45     build(mid+1,r,mid);46     f[now]=last;47     sz[mid]=sz[s[mid][0]]+sz[s[mid][1]]+1;48     if(mid<fa) s[last][0]=now;49     else s[last][1]=now;50 }51 int main(){52     scanf("%d%d",&n,&m);53     for(int i=1;i<=n+2;i++) id[i]=++hd;54     build(1,n+2,0);55     rt=(n+3)>>1;56     for(int i=1;i<=m;i++){57         int l,r;58         scanf("%d%d",&l,&r);59         rever(l,r);60     }61     for(int i=2;i<=n+1;i++) printf("%d ",find(rt,i)-1);62     return 0;63 }