学步园

传送门：【HDU】1890 Robotic Sort

题目分析：嗷，一个早上终于写出来了，总之splay还是不熟练啊，调死了。这次学到了几个操作，比如直接旋转出一个区间，这个操作要注意需要两个虚节点，最左端一个，最右端一个。23333写出来的感觉真爽啊~

感觉本题没什么好讲的。。。不会splay就去找资料学好了，splay对我来说目前只是调试烦。。。

代码如下：

/*
	void clear ()                       清空所有信息待下一次使用
	Node* newnode ( int v , Node* fa )  新建节点
	void rotate ( Node* o , int d )     旋转
	void splay ( Node* o , Node* t )    将o旋转到t的下面
	void select ( int k , Node* t )     找到第k个数并将其旋转到t的下面
	Node* get ( int l , int r )         找到区间[l,r]，令root = l - 1,root -> ch[1] = r + 1
	void reverse ( int l , int r )      翻转区间[l,r]
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

#define REP( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define CLR( a , x ) memset ( a , x , sizeof a )

const int MAXN = 100005 ;
const int INF = 0x3f3f3f3f ;

struct Node {
	Node* ch[2] ;
	Node* fa ;
	int v ;
	int s ;
	int rev ;
	int minv ;
	
	Node () {
		s = 0 ;
		v = minv = INF ;
		rev = 0 ;
	}
	
	int cmp ( int x ) {
		return x == v ? -1 : ( x < v ? 0 : 1 ) ;
	}
	
	void pushup () {
		s = 1 + ch[0] -> s + ch[1] -> s ;
		minv = min ( v , min ( ch[0] -> minv , ch[1] -> minv ) ) ;
	}
	
	void pushdown () ;
} Tnull , *null = &Tnull ;

void Node :: pushdown () {
	if ( !rev ) return ;
	rev = 0 ;
	swap ( ch[0] , ch[1] ) ;
	if ( ch[0] != null ) ch[0] -> rev ^= 1 ;
	if ( ch[1] != null ) ch[1] -> rev ^= 1 ;
}

struct Num {
	int x , idx ;
} ;

int cmpx ( const Num& a , const Num& b ) {
	return a.x < b.x ;
}

int cmpidx ( const Num& a , const Num& b ) {
	return a.idx < b.idx ;
}

struct Splay {
	Node node[MAXN] ;
	Node* root ;
	Node* cur ;
	
	Num num[MAXN] ;
	int n ;
	
	Splay () {
		cur = node ;
		root = null ;
	}
	
	void clear () {
		cur = node ;
		root = null ;
	}
	
	Node* newnode ( int v , Node* fa ) {
		cur -> ch[0] = cur -> ch[1] = null ;
		cur -> fa = fa ;
		cur -> s = 1 ;
		cur -> v = cur -> minv = v ;
		cur -> rev = 0 ;
		return cur ++ ;
	}
	
	void rotate ( Node* o , int d ) {
		Node* p = o -> fa ;
		p -> pushdown () ;
		o -> pushdown () ;
		p -> ch[d ^ 1] = o -> ch[d] ;
		o -> ch[d] -> fa = p ;
		o -> fa = p -> fa ;
		if ( p -> fa != null ) {
			if ( p == p -> fa -> ch[0] ) p -> fa -> ch[0] = o ;
			else p -> fa -> ch[1] = o ;
		}
		o -> ch[d] = p ;
		p -> fa = o ;
		p -> pushup () ;
		if ( root == p ) root = o ;
	}
	
	void splay ( Node* o , Node* t ) {
		while ( o -> fa != t ) {
			Node* p = o -> fa ;
			Node* gp = p -> fa ;
			if ( gp == t ) {
				if ( o == p -> ch[0] ) rotate ( o , 1 ) ;
				else rotate ( o , 0 ) ;
			} else {
				if ( p == gp -> ch[0] ) {
					if ( o == p -> ch[0] ) rotate ( p , 1 ) , rotate ( o , 1 ) ;
					else rotate ( o , 0 ) , rotate ( o , 1 ) ;
				} else {
					if ( o == p -> ch[1] ) rotate ( p , 0 ) , rotate ( o , 0 ) ;
					else rotate ( o , 1 ) , rotate ( o , 0 ) ;
				}
			}
		}
		o -> pushup () ;
	}
	
	void select ( int k , Node* t ) {
		Node* o = root ;
		++ k ;//空出虚拟节点的位置
		while ( o != null ) {
			o -> pushdown () ;
			int s = o -> ch[0] -> s ;
			if ( k == s + 1 ) break ;
			if ( k <= s ) o = o -> ch[0] ;
			else {
				k -= s + 1 ;
				o = o -> ch[1] ;
			}
		}
		splay ( o , t ) ;
	}
	
	Node* get ( int l , int r ) {
		select ( l - 1 , null ) ;
		select ( r + 1 , root ) ;
		return root -> ch[1] -> ch[0] ;
	}
	
	void reverse ( int l , int r ) {
		Node* o = get ( l , r ) ;
		o -> rev ^= 1 ;
		splay ( o , null ) ;
	}
	
	int find ( int x ) {
		Node* o = root ;
		int k = 0 ;
		while ( o != null ) {
			o -> pushdown () ;
			if ( o -> v == x ) {
				k += o -> ch[0] -> s + 1 ;
				break ;
			}
			if ( o -> ch[1] -> minv > x ) o = o -> ch[0] ;
			else {
				k += o -> ch[0] -> s + 1 ;
				o = o -> ch[1] ;
			}
		}
		return k - 1 ;
	}
	
	void init () {
		clear () ;
		FOR ( i , 0 , n + 1 ) {
			Node* o = newnode ( num[i].x , null ) ;
			o -> ch[0] = root ;
			root -> fa = o ;
			root = o ;
			root -> pushup () ;
		}
	}
	
	void solve () {
		num[0].x = num[n + 1].x = INF ;
		FOR ( i , 1 , n ) {
			scanf ( "%d" , &num[i].x ) ;
			num[i].idx = i ;
		}
		stable_sort ( num + 1 , num + n + 1 , cmpx ) ;
		FOR ( i , 1 , n ) num[i].x = i ;
		sort ( num + 1 , num + n + 1 , cmpidx ) ;
		init () ;
		FOR ( i , 1 , n ) {
			int k = find ( i ) ;
			printf ( "%d%c" , k , i < n ? ' ' : '\n' ) ;
			reverse ( i , k ) ;
		}
	}
} T ;

int main () {
	while ( ~scanf ( "%d" , &T.n ) && T.n )
		T.solve () ;
	return 0 ;
}