题意：给出初始序列a[n]=n
进行m次翻转，求最终序列。
只有在一开始，第几个点就是几号店。。。
在进行翻转后，如果还要翻转l-r，不是对l节点和r节点进行操作，而是对第l个和第r个点进行翻转。
首先，如果我们对整个序列建立平衡树，因为没有节点的增加和减少，所以整个数的结构建好了就不会改变。 即SBT的大小关系是下标，而不是值。
这样，就有了n个节点的线段树。
我们考虑怎么进行翻转，如果对整个序列进行翻转，只要把根的左右儿子互换，再把根的左儿子的左右儿子互换……交换所有的左右节点即可。那么，只要保证我们要修改的区间在平衡树的一棵子树中即可。
如何把区间变成一棵子树？设翻转l-r，只要把第l-1个节点（不是l-1号节点）splay到根，再把第r+1个节点splay到根的右儿子就行，这样以根的右儿子的左儿子为根的子树就是大于l-1，小于r+1，也就是l-r区间。
但有个问题，如果l=1或r=n呢？l-1=0，r+1>n，这就会出错，于是建树时我们把1-n的序列从2开始建到n+2，就可以避免这个问题。
至于翻转一颗子树，打lazy标记就行，pushdown的时候交换左右儿子
每次查找排名为n的点时pushdown就行
输出答案是对于每一个n，输出第n位（不是n号节点）的树就行。
要特别说说建树，直接在序列上建，如果一个一个插入太慢了，递归建树即可。
代码
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #define N 100010 using namespace std; int size[N],fa[N],tr[N][3],root,v[N],tmp[N],lazy[N],n,m,i,o,p; void pushup(int x) { size[x]=size[tr[x][0]]+size[tr[x][1]]+1; } void rotate(int x,int &rt) { int y=fa[x],z=fa[y],o,p; o=(tr[y][1]==x); p=!o; (y==rt?rt:tr[z][tr[z][0]!=y])=x; fa[x]=z; fa[y]=x; fa[tr[x][p]]=y; tr[y][o]=tr[x][p]; tr[x][p]=y; pushup(y); pushup(x); } void splay(int x,int &rt) { int y,z; while (x!=rt) { y=fa[x],z=fa[y]; if (y!=rt) { if ((tr[y][0]==x)^(tr[z][0]==y)) rotate(x,rt); else rotate(y,rt); } rotate(x,rt); } } void build(int father,int l,int r) { if (l>r) return; int mid=(l+r)/2; tr[father][mid>father]=mid; size[mid]=1; v[mid]=tmp[mid]; fa[mid]=father; if (l==r) return; build(mid,l,mid-1); build(mid,mid+1,r); pushup(mid); } void pushdown(int x) { if (!lazy[x]) return; lazy[x]^=1; swap(tr[x][0],tr[x][1]); lazy[tr[x][0]]^=1; lazy[tr[x][1]]^=1; return; } int find(int x) { int rt=root; while (1) { pushdown(rt); if (x<=size[tr[rt][0]]) { rt=tr[rt][0]; continue; } x-=size[tr[rt][0]]; if (x==1) return rt; x--; { rt=tr[rt][1]; continue; } } } void rever(int x,int y) { x=find(x); y=find(y); splay(x,root); splay(y,tr[root][1]); lazy[tr[y][0]]^=1; return ; } int main() { scanf("%d %d",&n,&m); for (i=2;i<=n+1;i++) tmp[i]=i-1; build(0,1,n+2); root=(n+3)/2; //(2 + n+1)/2 for (i=1;i<=m;i++) { scanf("%d %d",&o,&p); rever(o,p+2); } for (i=2;i<=n+1;i++) { printf("%d ",v[find(i)]); } return 0; }