模板题。
注意标记即可,另外,涉及区间翻转操作,记得设立首尾哨兵。
#include<bits/stdc++.h>
using namespace std;
const int Maxn=0x3f3f3f3f;
const int N=1e5+5;
int lc[N],rc[N],fa[N],sze[N],vi[N],pos[N],a[N];
int n,m,x,y,rt,T;
inline int get(){//快读
char ch;bool f=false;int res=0;
while(((ch=getchar())<'0'||ch>'9')&&ch!='-');
if(ch=='-') f=true;
else res=ch-'0';
while((ch=getchar())>='0'&&ch<='9')
res=(res<<3)+(res<<1)+ch-'0';
return f?~res+1:res;
}
inline bool Wrt(const int&x)
{
return rc[fa[x]]==x;
}
inline void down(const int &x){//下传标记
if(x&&pos[x]){
pos[lc[x]]^=1;
pos[rc[x]]^=1;
swap(lc[x],rc[x]);
pos[x]=0;
}
}
inline void push(int x){
sze[x]=sze[lc[x]]+sze[rc[x]]+1;
}
inline int build(int lst,int l,int r){//lst该节点的祖先编号
if(l>r) return 0;
int mid=(l+r)>>1,x=++T;
fa[x]=lst;pos[x]=0;vi[x]=a[mid];
lc[x]=build(x,l,mid-1);
rc[x]=build(x,mid+1,r);
push(x);
return x;
}
inline void rot(int x){//单旋
int y=fa[x],z=fa[y];
down(y);down(x);//下传标记
int b=(lc[y]==x)?rc[x]:lc[x];
fa[x]=z;fa[y]=x;
if(b) fa[b]=y;
if(z) (y==lc[z]?lc[z]:rc[z])=x;
if(x==lc[y]) rc[x]=y,lc[y]=b;
else lc[x]=y,rc[y]=b;
push(y);push(x);//更新
}
inline void splay(int x,int tar){
while(fa[x]!=tar){
if(fa[fa[x]]!=tar)
Wrt(x)==Wrt(fa[x])?rot(fa[x]):rot(x);
rot(x);
}
if(!tar) rt=x;
}
inline int Find(int k){//查找第k个数
int x=rt,y=k;
while(x){
down(x);
if(y<=sze[lc[x]]) x=lc[x];
else{
y-=sze[lc[x]]+1;
if(!y) return x;
x=rc[x];
}
}
}
/*inline void put(int x){//快输
if(x<0){
x=~x+1;
putchar('-');
}
if(x>9) put(x/10);
putchar(x%10+48);
}*/
inline void Print(int x){
down(x);
if(lc[x]) Print(lc[x]);
if(vi[x]!=-Maxn&&vi[x]!=Maxn)
// put(vi[x]),putchar(' ');//快输
cout<<vi[x]<<" ";
if(rc[x]) Print(rc[x]);
}
int main(){
n=get();m=get();
a[1]=-Maxn;a[n+2]=Maxn;
for(int i=1;i<=n;i++) a[i+1]=i;
rt=build(0,1,n+2);
while(m--){
int tx=Find(get());
int ty=Find(get()+2);
splay(tx,0);
splay(ty,tx);
pos[lc[rc[rt]]]^=1;
}
return Print(rt),0;
}