伸展树对于区间的翻转操作尤其的方便。
对于区间翻转的时候，同样使用lazy标记。
但是在splay操作的时候注意要先更新孩子，然后在判断改左旋还是右旋。
#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> using namespace std; #define maxn 110000 #define mem(a,b) memset(a,b,sizeof(a)) struct splaytree {int pre[maxn];int ch[maxn][2];int key[maxn];int rev[maxn];int size[maxn];int val[maxn];int sum[maxn];int root,tot;int n;void Treaval(int x){if(x){Treaval(ch[x][0]);printf("结点%2d:左儿子 %2d 右儿子 %2d 父结点 %2d size = %2d ,val = %2d , sum = %2d \n",x,ch[x][0],ch[x][1],pre[x],size[x],val[x],sum[x]);Treaval(ch[x][1]);}}void debug(){printf("%d\n",root);Treaval(root);}//debug专用struct list{int x;int st;friend bool operator < (const list &a,const list &b){if(a.x!=b.x)return a.x<b.x;return a.st<b.st;}} node[maxn];void init(){root=tot=0;mem(pre,0);mem(ch,0);mem(rev,0);mem(size,0);}void newnode(int &x,int father,int k){x=k;pre[x]=father;ch[x][0]=ch[x][1]=0;rev[x]=0;key[x]=k;size[x]=1;}void push_down(int x){if(rev[x]){rev[ch[x][0]]^=1;rev[ch[x][1]]^=1;swap(ch[x][0],ch[x][1]);rev[x]=0;}}void push_up(int x){size[x]=size[ch[x][0]]+size[ch[x][1]]+1;}void rot(int x,int kind){int y=pre[x];push_down(y);push_down(x);ch[y][!kind]=ch[x][kind];pre[ch[x][kind]]=y;if(pre[y])ch[pre[y]][ch[pre[y]][1]==y]=x;pre[x]=pre[y];ch[x][kind]=y;pre[y]=x;push_up(y);push_up(x);}void splay(int x,int goal){push_down(x);while(pre[x]!=goal){if(pre[pre[x]]==goal){push_down(pre[x]);push_down(x);rot(x,ch[pre[x]][0]==x);}else{int y=pre[x];push_down(pre[y]);push_down(pre[x]);push_down(x);int kind=ch[pre[y]][0]==y;if(ch[y][kind]==x){rot(x,!kind);rot(x,kind);}else{rot(y,kind);rot(x,kind);}}}push_up(x);if(goal==0)root=x;}int getmax(int x){push_down(x);while(ch[x][1]){x=ch[x][1];push_down(x);}return x;}void erase(int x){if(ch[root][0]==0){root=ch[root][1];pre[root]=0;}else{int m=getmax(ch[root][0]);splay(m,root);ch[m][1]=ch[root][1];pre[ch[root][1]]=m;root=m;pre[root]=0;push_up(root);}}void buildtree(int &x,int l,int r,int father){if(l>r)return ;int mid=(l+r)/2;// cout<<x<<"--->";newnode(x,father,mid);// cout<<x<<endl;buildtree(ch[x][0],l,mid-1,x);buildtree(ch[x][1],mid+1,r,x);push_up(x);}void start(){sort(node+1,node+n+1);buildtree(root,1,n,0);} } T; int main() {int n,i;while(scanf("%d",&n)!=EOF&&n){T.init();T.n=n;for(i=1; i<=n; i++){scanf("%d",&T.node[i].x);T.node[i].st=i;}T.start();// T.debug();for(int i=1; i<n; i++){//T.debug();T.splay(T.node[i].st,0);T.rev[T.ch[T.root][0]]^=1;printf("%d ",i+T.size[T.ch[T.root][0]]);T.erase(T.root);}printf("%d\n",n);}return 0; }