解法
splay的基本操作加上一个区间翻转。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int read()
{
int x=0,p=1; char ch=getchar();
while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
if(ch=='-') p=-1,ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*p;
}
int ch[N][2],par[N],val[N],cnt[N],siz[N],rev[N],tot,root;
int n,m;
bool chk(int x) { return ch[par[x]][1]==x; }
void pushup(int x) { siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+cnt[x]; }
void pushdown(int x)
{
if(rev[x])
{
swap(ch[x][1],ch[x][0]);
rev[ch[x][0]]^=1;
rev[ch[x][1]]^=1;
rev[x]=0;
}
}
void rotate(int x)
{
int y=par[x],z=par[y],k=chk(x),w=ch[x][k^1];
ch[y][k]=w,par[w]=y;
ch[z][chk(y)]=x,par[x]=z;
ch[x][k^1]=y,par[y]=x;
pushup(y); pushup(x);
}
void splay(int x,int goal)
{
int y,z;
while(par[x]!=goal)
{
y=par[x],z=par[y];
if(z!=goal)
chk(x)==chk(y) ? rotate(y):rotate(x);
rotate(x);
}
if(!goal) root=x;
}
void insert(int x)
{
int u=root,p=0;
while(u && val[u]!=x) p=u,u=ch[u][x>val[u]];
if(u) cnt[u]++;
else
{
u=++tot;
if(p) ch[p][x>val[p]]=u;
ch[u][0]=ch[u][1]=0;
par[u]=p; val[u]=x;
cnt[u]=siz[u]=1;
}
splay(u,0);
}
int kth(int k)
{
int u=root;
while(1)
{
pushdown(u);
if(ch[u][0] && k<=siz[ch[u][0]]) u=ch[u][0];
else if(k>siz[ch[u][0]]+cnt[u]) k-=siz[ch[u][0]]+cnt[u],u=ch[u][1];
else return u;
}
}
void reverse(int l,int r)
{
int L=kth(l),R=kth(r+2);
splay(L,0),splay(R,L);
rev[ch[R][0]]^=1;
}
void output(int x)
{
pushdown(x);
if(ch[x][0]) output(ch[x][0]);
if(val[x] && val[x]<=n) printf("%d ",val[x]);
if(ch[x][1]) output(ch[x][1]);
}
int main()
{
//freopen("data.in","r",stdin);
//freopen("my.out","w",stdout);
n=read(),m=read();
for(int i=0;i<=n+1;i++) insert(i);
while(m--)
{
int x=read(),y=read();
reverse(x,y);
}
output(root);
return 0;
}