题面：
思路：
一看到要在序列里面翻转一段区间，就知道要使用splay了
但是这道题涉及到一个问题：如何在通过序列位置定义的splay上面查找最小值？
（对splay的这种用法不熟悉的可以参考这篇博客）
这里提供两种方法：
第一种，对于每一个splay节点，我们把它的键值w设为它在原序列中的排名（注意：相同的数排名不同，这一步需要离散化）
然后再保存一个min值即可
这样每一次我们想要在splay树中找大小最小的节点，只要不断地往min小一些的方向去走即可
然后，当我们做完一次操作（翻转）以后，因为前面已经排好序的元素我们其实不用再管它了，所以可以把这个元素从splay中删掉
这样，以后每次要翻转到前面去的，都是当前splay里面最小的那个元素了
这种方式的优点在于找最小值的过程比较直观，但是需要多维护一个min值，调试难度略大
第二种，不保存min值，而是选取另一个方法：映射
在输入数据、离散化结束以后，我们用二叉构造的方式建splay，这个过程中会给每一个元素赋一个“这个元素在splay数组中的下标”
我们建立一个pos数组来保存从元素到这个数组下标的映射，即pos[i]的值代表“第i个元素在splay数组当中的下标”
这样的话，每一次操作时我们可以通过把这个已知的元素splay到根的方式，得到它在当前splay中的排名，用这个排名加上前面已经处理完了的数的个数，就得到了当前未操作序列中最小元素（也就是下一步需要操作的元素）的位置了
然后再把它旋转、删除即可
这种方式的优点在于没用在splay上维护更多量，缺点是时间效率可能会比较低
Code：
由于博主比较懒，虽然两种方法都想到了，但是只写了第二种......
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define inf 1e9 6 using namespace std; 7 inline int read(){ 8 int re=0,flag=1;char ch=getchar(); 9 while(ch>'9'||ch<'0'){ 10 if(ch=='-') flag=-1; 11 ch=getchar(); 12 } 13 while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar(); 14 return re*flag; 15 } 16 int n,m,cnt,root,pos[200010]; 17 int fa[200010],ch[200010][2],rev[200010],siz[200010],w[200010]; 18 struct node{ 19 int val,num; 20 }a[200010]; 21 bool cmp(node l,node r){ 22 if(l.val!=r.val) return l.val<r.val; 23 else return l.num<r.num; 24 } 25 bool cmp2(node l,node r){ 26 return l.num<r.num; 27 } 28 void _swap(int &l,int &r){l^=r;r^=l;l^=r;} 29 void update(int x){ 30 siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1; 31 } 32 void pushrev(int x){ 33 if(!x) return; 34 _swap(ch[x][0],ch[x][1]); 35 rev[x]^=1; 36 } 37 int push(int x){ 38 if(x&&rev[x]){ 39 pushrev(ch[x][0]);pushrev(ch[x][1]); 40 rev[x]=0; 41 } 42 return 1; 43 } 44 int get(int x){return ch[fa[x]][1]==x;} 45 void rotate(int x){ 46 int f=fa[x],ff=fa[f],son=get(x); 47 push(f);push(x); 48 ch[f][son]=ch[x][son^1]; 49 if(ch[f][son]) fa[ch[f][son]]=f; 50 fa[f]=x;ch[x][son^1]=f; 51 fa[x]=ff; 52 if(ff) ch[ff][ch[ff][1]==f]=x; 53 update(f);update(x); 54 } 55 void splay(int x,int to){ 56 push(x); 57 for(int f;(f=fa[x])&&(f!=to);rotate(x)){ 58 push(fa[f]);push(f);push(x); 59 if(fa[f]!=to) 60 rotate((get(x)==get(f))?f:x); 61 } 62 update(x); 63 if(!to) root=x; 64 } 65 int build(int l,int r,int f){ 66 if(l>r) return 0; 67 int cur=++cnt,mid=(l+r)>>1; 68 fa[cur]=f;w[cur]=a[mid].val;siz[cur]=1;pos[a[mid].val]=cur; 69 ch[cur][0]=build(l,mid-1,cur); 70 ch[cur][1]=build(mid+1,r,cur); 71 // cout<<"finish build "<<mid<<ends<<cur<<ends<<ch[cur][0]<<ends<<ch[cur][1]<<endl; 72 update(cur);return cur; 73 } 74 void dfs(int u){ 75 if(!u) return; 76 dfs(ch[u][0]); 77 cout<<u<<ends<<w[u]<<ends<<rev[u]<<ends<<ch[u][0]<<ends<<ch[u][1]<<ends<<siz[u]<<endl; 78 dfs(ch[u][1]); 79 } 80 void init(){ 81 memset(fa,0,sizeof(fa));memset(ch,0,sizeof(ch));memset(rev,0,sizeof(rev)); 82 memset(siz,0,sizeof(siz));memset(w,0,sizeof(w));memset(a,0,sizeof(a)); 83 root=0,cnt=0; 84 } 85 int suf(){ 86 push(root); 87 int x=ch[root][1]; 88 while(push(x)&&ch[x][0]) x=ch[x][0]; 89 return x; 90 } 91 void reverse(int p){ 92 // cout<<"reverse "<<p<<endl; 93 splay(pos[p],0); 94 printf("%d",p-1+siz[ch[root][0]]); 95 if(p!=n) printf(" "); 96 int x=pos[0],y=suf(); 97 splay(x,0);splay(y,root); 98 // dfs(root); 99 pushrev(ch[y][0]); 100 } 101 void del(int p){ 102 // cout<<"del "<<p<<endl; 103 splay(pos[p],0);int tmp=suf(); 104 splay(pos[0],0);splay(tmp,root); 105 fa[ch[tmp][0]]=0;ch[tmp][0]=0;update(tmp);update(pos[0]); 106 // dfs(root); 107 // cout<<"dell "<<p<<endl; 108 // fa[ch[root][1]]=ch[root][0];ch[ch[root][0]][1]=ch[root][1]; 109 // update(ch[root][0]);root=ch[root][0];fa[root]=0; 110 // fa[ch[root][0]]=tmp;ch[tmp][0]=ch[root][0]; 111 // update(tmp);root=tmp;fa[tmp]=0; 112 // dfs(root); 113 } 114 int main(){ 115 // freopen("a.txt","w",stdout); 116 int i,t1; 117 while(n=read()){ 118 init(); 119 for(i=1;i<=n;i++) a[i].val=read(),a[i].num=i; 120 sort(a+1,a+n+1,cmp); 121 // for(i=1;i<=n;i++) cout<<a[i].val<<ends<<a[i].num<<endl; 122 for(i=1;i<=n;i++) a[i].val=i; 123 sort(a+1,a+n+1,cmp2); 124 a[0].val=0;a[n+1].val=n+1; 125 // for(i=0;i<=n+1;i++) cout<<a[i].val<<ends;cout<<endl; 126 root=build(0,n+1,root); 127 for(i=1;i<=n;i++){ 128 reverse(i);del(i); 129 } 130 printf(" "); 131 } 132 }