题目链接：HDU1890

【题意】给出一个无序序列，请用翻转的方法给它排序：翻转的起点依次递增，输出每次翻转的终点。比如3 4 5 1 6 2这个序列，最小的元素在4位置，第一遍排序的时候以1为起点4为终点转后为1 5 4 3 6 2；第二遍的时候最小的在位置6，则以2为起点6为终点转成1 2 6 3 4 5；第三遍最小的在4，旋转3 4；。。。。。。

【分析】一开始始终想怎样用splay来存下标或者值，维护这个splay，而实际上不需要记录值，只要维护一个sz，splay下标就是初始数组的下标，然后对所有值按照值和下标排序(值先排)，接下来每次按照顺序，则就是当前最小的值(根据记录的id能直接找到splay的结点)，然后把这个结点伸展到根，此时他的左儿子的sz+1+i就是答案；这题让我学会了splay从下往上的更新，原来从上往下的splay没法根据结点伸展，只能伸展第几个(第几大)；代码中splay的v可以不用记录，这里是为了调试才用的

【AC CODE】296ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <map>
//#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 3*100000+10;
/* 从下往上伸展的splay */
struct NODE{
     NODE *ch[2], *fa;
     int sz,v;//sz-当前子树有多少个结点,v-结点值
    bool f;//lazy标记
    int chd(){//当前结点是左儿子还是右儿子,返回0-左儿子,1-右儿子
        return this == fa->ch[1];
     }
     void push_up(){
         sz = ch[0]->sz+ch[1]->sz+1;
     }
     void push_down(){
         if(f){
             f = false;
             swap(ch[0],ch[1]);
             ch[0]->f ^= 1;
             ch[1]->f ^= 1;
         }
     }
};
 NODE *null = new NODE;
inline void setch(NODE *fa, NODE *u, int p)//重置关联的儿子和父亲,p=0表示u是fa的左儿子1是右儿子
{
     fa->ch[p] = u, u->fa = fa;
}
void rot(NODE *u)//旋转
{
     NODE*y = u->fa;
     int d = u->chd();//决定是左旋还是右旋d=0左儿子对应右旋,d=1右儿子对应左旋
    setch(y->fa,u,y->chd());//把y的父亲(就是u父亲的父亲)的y儿子变为u =====把u放到当前根
    setch(y,u->ch[d^1],d);//把u的对应儿子放到u所在位置(此时变成两颗树了 y成另外一颗树的根)
     setch(u,y,d^1);//把y放到u的对应儿子
    y->push_up(), u->push_up();//先更新y再更新u(y在u下面了)
}
/* =================== splay1->start ===========================================*/
void dfs_down(NODE *x)//先把根到x所用到的所有的标记下放
{
     if(x == null)return;
     dfs_down(x->fa);
     x->push_down();//保证从上往下push_down
}
void splay(NODE* &rt,NODE *x, NODE *p)//把rt树的x节点伸展到p下方(即p的儿子),从下往上伸展，x != p
{
     dfs_down(x);
     while(x->fa != p)
     {
         NODE *y = x->fa;
         if(x->fa->fa != p && x->chd() == y->chd()) rot(y);
         rot(x);
     }
     if(p == null) rt = x;
}
/* =================== splay1->end ===========================================*/
/* =================== splay2->start ===========================================*/
/*NODE* find_kth(NODE *u, int k)//寻找第k小的结点(数列从左往右第k个),u为splay的根
{
     u->push_down();
     int d = k - u->ch[0]->sz;
     if(1 == u->sz) return u;//找到
    if(d <= 0) return find_kth(u->ch[0],k);//往左
    return find_kth(u->ch[1],k-u->ch[0]->sz-1);//往右
}
void splay(NODE* &rt,int k, NODE *p)//把rt树第k大结点(数列从左往右第k个)伸展到p下面
{
     NODE *x = find_kth(rt,k);
     while(x->fa != p)
     {
         NODE *y = x->fa;
         if(x->fa->fa != p && x->chd() != y->chd()) rot(y);
         rot(x);
     }

 }*/
/* =================== splay2->end ===========================================*/
void del(NODE* &rt,NODE *x)//删除rt树的结点x
{
     NODE *u = x->ch[0], *v = x->ch[1];
     if(null == u) setch(null,v,1);//如果没有左儿子就把右儿子设为根
    else if(null == v) setch(null,u,1);//没有左儿子就把左儿子设为根,左右都没的话就变成空树了
    else
     {
         //左右儿子都存在时分别找出x左边和x右边的结点
        u->push_down(), v->push_down();
         while(u->ch[1] != null){u = u->ch[1], u->push_down();}
         while(v->ch[0] != null){v = v->ch[0], v->push_down();}
         //把x左边的u伸展到根，把x右边的v伸展到u下面
        splay(rt,u,null), splay(rt,v,u);
         v->ch[0] = null;
     }
}
/*合并left和right，假定left所有元素都比right小；right可以是NULL，但left不可以*/
/*NODE* merge(NODE *left, NODE *right)
 {
     splay(left,left->sz,null);//把left中序顺序最后一个结点 伸展到根,这样left就没有右子树了
    left->ch[1] = right;//把right接到left的右子树
    left->push_up();//更新根节点需要维护的值
}*/
/*分裂u,把u前k小结点放在left,其他放在right; 1<= k <=u->sum当k==u->sum时right=NULL,u不能空*/
/*void split(NODE *u, int k, NODE *left, NODE *right)
 {
     splay(u,k,null);//把u的第k小的结点伸展到u的根
    right = u->ch[0];//u的右儿子就是right
     left = u;//u的左儿子以及u就是left，右儿子改为null
     u->ch[1] = null;
     left->push_up();//只需要更新左儿子，右儿子不需要更新
}*/
struct SplayTree{
     NODE node[MAXN];
     NODE *rt;
     void bulid(NODE* &u, int x, int y, NODE *fa)
     {
         if(x>y)
         {
             u = null;
             return;
         }
         int m = (x+y)>>1;
         u = &node[m];
         u->fa = fa;
         u->f = 0;
         u->v = m;
         bulid(u->ch[0],x,m-1,u);
         bulid(u->ch[1],m+1,y,u);
         u->push_up();
     }
     void init(int sz)
     {
         null->sz = 0;
         null->ch[0] = null->ch[1] = null->fa = null;
         bulid(rt,1,sz,null);
     }
}s;
void pt(NODE *u)
{
     if(null == u) return;
     pt(u->ch[0]);
     printf("%d\n", u->v);
     pt(u->ch[1]);
}
typedef pair<int,int> P;
 P a[MAXN];

int main()
{
#ifdef SHY
     freopen("e:\\1.txt", "r", stdin);
#endif
     int n;
     while(~scanf("%d%*c", &n) && n)
     {
         repe(i,1,n)
         {
             scanf("%d%*c", &a[i].first);
             a[i].second = i;
         }
         s.init(n);
         sort(a+1,a+n+1);
         repe(i,1,n)
         {
             //把因为node[]的下标和a[]下标是一样的，所以根据排序后的编号可以直接伸展上来
            NODE *x = &s.node[a[i].second];
             splay(s.rt,x,null);//把x伸展到根
            x->ch[0]->f ^= 1;
             printf("%d", s.rt->ch[0]->sz+1+i-1);
             if(i == n) putchar('\n');
             else putchar(' ');
             del(s.rt,x);
         }
     }
     return 0;
}