题解 P3391 【【模板】文艺平衡树（Splay）】
此解法为一种基于复杂度平衡思想的链表信息维护算法
关于此类问题的另一种同复杂度算法：块状链表 在此不做阐述。
文艺平衡树
可以发现假使此序列为一个链表,第一个c点表示为观察点，r点为另一个观察点，d点为第一个序列点，如图所示：
假使进行一段区间的反转，如图所示：
可以将相关两条链删除，如图所示：
连上新链，如图所示:
显然，由于观察点的位置必定不变，自观察点开始向后遍历输出即为答案。
那么对于每次修改，寻找到区间两头的确切点就是必要的。
显然每次从观察点依次向后跳的复杂度为O（n），那么如何快速找到某位置的点就是解决问题的关键。
假若进行倍增的跳跃方式，那么每次寻找的复杂度是O（logn）的，但进行修改后的更新复杂度却是O（nlogn）的，显然无法使用。
此时假若每个点不再存储logn个向后跳的边（即倍增数组），改为只存储第一个相邻的点和距离自己k（常数）距离的点，以观察点为例，且此时k=3，如图所示：
此时寻找操作只需先每次跳到距离自己为k的点，直到距离不超过k时再依次向后跳，此时复杂度为O(max(n/k,k))。
关于修改，假若对如下区间反转，如图所示：
那么涉及到相邻点的边只有两个修改，而关于长度为k的边（此时k=3）对于反转区间内需要修改的点仅为如图横线下所示6（min(2k,r-l+1)）个点，易证区间外需要修改的点数也不超过2k个。
因为相距修改区间距离超过k的点必定不会被涉及，所以可知修改复杂度为O(k)。
此时发现两种操作呈乘积相关，根据复杂度平衡可知k取sqrt(n)时理论复杂度最低，总体为O(n*sqrt(n))。
最后自观察点向后遍历输出即为本题最终答案。
本代码由于常数问题无法通过本题
#include<bits/stdc++.h>
using namespace std;
int n,m,k,nxt[100007][2],f[100007][2];
inline void init(){
memset(nxt,-1,sizeof(nxt));memset(f,-1,sizeof(f));
nxt[0][1]=1;f[0][1]=k;
for(int i=1;i<=n;i++){
nxt[i][0]=i-1;nxt[i][1]=i+1;
if(i-k>=0)f[i][0]=i-k;if(i+k<=n)f[i][1]=i+k;
}
nxt[n+1][0]=n;f[n+1][0]=n-k;
}
inline void go_slow(int &x,bool &to){int u=nxt[x][to];to^=(nxt[u][to^1]!=x);x=u;}
inline void go_fast(int &x,bool &to){int u=f[x][to];to^=(f[u][to^1]!=x);x=u;}
inline int find(int x,bool &to){
if(x>n||x<0)return -1;
int now=0;to=1;register int i;
for(i=1;i<=x/k;i++)go_fast(now,to);
for(i=1;i<=x%k;i++)go_slow(now,to);
return now;
}
inline void update(int x,bool tox,int y,bool toy,int len){
for(int i=1;i<=min(k,len);i++){
int g=x;bool tt=tox^1;
go_fast(g,tt);f[g][tt^1]=y;
g=y;tt=toy^1;
go_fast(g,tt);f[g][tt^1]=x;
swap(f[x][tox^1],f[y][toy^1]);
go_slow(x,tox);go_slow(y,toy);
}
}
signed main(){
scanf("%d%d",&n,&m);k=sqrt(n);init();
int x,y,len,g;bool tox,toy,tt;
while(m--){tox=1;toy=1;
scanf("%d%d",&x,&y);len=y-x+1;
x=find(x,tox);y=find(y,toy);
update(x,tox,y,toy^1,len);
g=x;tt=tox^1;
go_slow(g,tt);nxt[g][tt^1]=y;
g=y;tt=toy;
go_slow(g,tt);nxt[g][tt^1]=x;
swap(nxt[x][tox^1],nxt[y][toy]);
}
int now=0;bool tonow=1;
for(int i=1;i<=n;++i)go_slow(now,tonow),printf("%d ",now);
return 0;
}