小奇成功打开了大科学家的电脑。
大科学家打算前往n处景点旅游，他用一个序列来维护它们之间的顺序。初
始时，序列为1,2,...,n。
接着，大科学家进行m次操作来打乱顺序。每次操作有6步：
1、从序列开头（左端）取出A个数（此时序列剩下n-A个数）
2、从序列开头取出B个数
3、将第1步取出的A个数按原顺序放回序列开头
4、从序列开头取出C个数
5、将第2步取出的B个数逆序放回序列开头
6、将第4步取出的C个数按原顺序放回序列开头
你需要求出最终序列。
题解：Splay裸题，但是不要全部按他告诉你的做。每次操作相当于将区间[A+1,A+B]挪到(C,C+1)中间。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=100010;
int n,m,rt,A,B,C;
struct node
{
int ch[2],fa,siz,rev;
}s[maxn];
inline void pushup(int x)
{
s[x].siz=s[s[x].ch[0]].siz+s[s[x].ch[1]].siz+1;
}
inline void pushdown(int x)
{
if(s[x].rev)
{
swap(s[x].ch[0],s[x].ch[1]);
if(s[x].ch[0]) s[s[x].ch[0]].rev^=1;
if(s[x].ch[1]) s[s[x].ch[1]].rev^=1;
s[x].rev=0;
}
}
inline void rotate(int x,int &k)
{
int y=s[x].fa,z=s[y].fa,d=(x==s[y].ch[1]);
if(y==k) k=x;
else s[z].ch[y==s[z].ch[1]]=x;
s[x].fa=z,s[y].ch[d]=s[x].ch[d^1],s[y].fa=x;
if(s[x].ch[d^1]) s[s[x].ch[d^1]].fa=y;
s[x].ch[d^1]=y;
pushup(y),pushup(x);
}
inline void splay(int x,int &k)
{
while(x!=k)
{
int y=s[x].fa,z=s[y].fa;
if(y!=k)
{
if((y==s[z].ch[0])^(x==s[y].ch[0])) rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
}
int find(int x,int y)
{
if(!x) return 0;
pushdown(x);
if(y<=s[s[x].ch[0]].siz) return find(s[x].ch[0],y);
if(y>s[s[x].ch[0]].siz+1) return find(s[x].ch[1],y-s[s[x].ch[0]].siz-1);
return x;
}
int build(int l,int r,int last)
{
if(l>r) return 0;
int x=(l+r)>>1;
s[x].fa=last,s[x].siz=r-l+1;
s[x].ch[0]=build(l,x-1,x);
s[x].ch[1]=build(x+1,r,x);
return x;
}
void dfs(int x)
{
if(!x) return ;
pushdown(x);
dfs(s[x].ch[0]);
if(x>1&&x<n+2) printf("%d ",x-1);
dfs(s[x].ch[1]);
}
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<‘0‘||gc>‘9‘) {if(gc==‘-‘) f=-f; gc=getchar();}
while(gc>=‘0‘&&gc<=‘9‘) ret=ret*10+gc-‘0‘,gc=getchar();
return ret*f;
}
int main()
{
n=rd(),m=rd();
int i,x;
rt=build(1,n+2,1);
for(i=1;i<=m;i++)
{
A=rd(),B=rd(),C=rd();
splay(find(rt,A+1),rt),splay(find(rt,A+B+2),s[rt].ch[1]);
x=s[s[rt].ch[1]].ch[0],s[s[rt].ch[1]].ch[0]=0,pushup(s[rt].ch[1]),pushup(rt);
s[x].rev^=1;
splay(find(rt,C+1),rt),splay(find(rt,C+2),s[rt].ch[1]);
s[s[rt].ch[1]].ch[0]=x,s[x].fa=s[rt].ch[1],pushup(s[rt].ch[1]),pushup(rt);
}
dfs(rt);
return 0;
}
原文：http://www.cnblogs.com/CQzhangyu/p/7747174.html