记录编号	91511	评测结果	A
题目名称	[UVa 1402] 机器排序	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.261 s
提交时间	2014-03-14 22:31:28	内存使用	1.46 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int SIZEN=100010,INF=0x7fffffff/2;
class SPLAYTREE{
public:
	class NODE{
	public:
		int key,size;
		bool rev;
		NODE *f,*lc,*rc;
		int mx;//子树上最小值
		NODE(int k){key=mx=k;size=1;rev=0;}
	}*Nil,*Root,*left,*right;
	void print(NODE *t){//调试接口,输出节点信息
		cout<<"key:"<<t->key;
		cout<<" size:"<<t->size<<" rev:"<<t->rev<<" mx:"<<t->mx<<endl;
		cout<<"father:";
		(t->f==Nil?cout<<"Nil":cout<<t->f->key);
		cout<<" lc:";
		(t->lc==Nil?cout<<"Nil":cout<<t->lc->key);
		cout<<" rc:";
		(t->rc==Nil?cout<<"Nil":cout<<t->rc->key)<<endl<<endl;
		if(t->lc!=Nil) print(t->lc);
		if(t->rc!=Nil) print(t->rc);
	}
	void print(void){//调试接口,输出树
		cout<<"Nil:"<<Nil<<endl;
		cout<<"left:"<<left<<endl;
		cout<<"right:"<<right<<endl;
		cout<<"Root:"<<Root<<endl;
		print(Root);
	}
	void printlis(NODE *t){//调试接口,输出子树序列
		if(!t->rev){
			if(t->lc!=Nil) printlis(t->lc);
			cout<<t->key<<" ";
			if(t->rc!=Nil) printlis(t->rc);
		}
		else{
			if(t->rc!=Nil) printlis(t->rc);
			cout<<t->key<<" ";
			if(t->lc!=Nil) printlis(t->lc);
		}
	}
	void printlis(void){//调试接口,输出序列
		printlis(Root);
		cout<<endl;
	}
	NODE *newNODE(int key){//新建一个节点,将其父子都指向Nil
		NODE *T=new NODE(key);
		T->lc=T->rc=T->f=Nil;
		return T;
	}
	void clear(){//清空这棵树,此时树中几乎没有节点(被删完了)
		Nil=new NODE(INF);
		Nil->lc=Nil->rc=Nil->f=Nil;
		Nil->size=0;
		left=newNODE(INF),right=newNODE(INF);
		left->size++,left->rc=right,right->f=left;//建立初始树:左哨兵的右儿子是右哨兵,根是左哨兵
		Root=left;
	}
	void pushdown(NODE *T){//下压翻转信息
		if(T->rev){
			T->lc->rev^=1,T->rc->rev^=1;
			swap(T->lc,T->rc);
			T->rev=0;
		}
	}
	void update(NODE *T){//更新最值
		T->size=T->lc->size+T->rc->size+1;
		T->mx=min(T->lc->mx,T->rc->mx);
		T->mx=min(T->mx,T->key);
	}
	void zig(NODE *T){//右旋
		NODE *P=T->f,*rson=T->rc;
		pushdown(P->rc),pushdown(T->lc),pushdown(T->rc);
		if(Root==P) Root=T;
		else (P->f->lc==P)?(P->f->lc=T):(P->f->rc=T);
		T->f=P->f,P->f=T;rson->f=P;T->rc=P;P->lc=rson;
		update(P);
	}
	void zag(NODE *T){//左旋
		NODE *P=T->f,*lson=T->lc;
		pushdown(P->lc),pushdown(T->lc),pushdown(T->rc);
		if(Root==P) Root=T;
		else (P->f->lc==P)?(P->f->lc=T):(P->f->rc=T);
		T->f=P->f,P->f=T;lson->f=P;T->lc=P;P->rc=lson;
		update(P);
	}
	void splay(NODE *ANC,NODE *t){//把t旋转到ANC
		pushdown(t);
		if(t==ANC){update(t);return;}
		bool reach=false;
		while(!reach){
			NODE *P=t->f;
			if(P==ANC) (P->lc==t)?zig(t):zag(t),reach=true;
			else{
				if(P->f==ANC) reach=true;
				if(P->f->lc==P) (P->lc==t)?zig(P):zag(t),zig(t);
				else (P->rc==t)?zag(P):zig(t),zag(t);
			}
		}
		update(t);
	}
	void insert(int *a,int k){//初始化为a[1]~a[k]
		NODE *t=newNODE(a[1]),*p=t,*q=t;
		for(int i=2;i<=k;i++) t=newNODE(a[i]),t->f=p,p->rc=t,p=t;
		Root->rc->lc=q,q->f=Root->rc;//直接向初始树右哨兵的左子树插就行了
		splay(Root,p);
	}
	void select(NODE *ANC,int k){//把ANC的子树中第k个节点提到ANC原先的位置
		NODE *t=ANC;
		while(true){
			pushdown(t);
			if(k==t->lc->size+1){
				splay(ANC,t);
				return;
			}
			if(k<=t->lc->size) t=t->lc;
			else k-=t->lc->size+1,t=t->rc;
		}
	}
	void findmin(int k){
		NODE *t=Root;
		int pos=0;
		while(t->key!=t->mx){
			pushdown(t);
			if(t->lc->mx==t->mx) t=t->lc;
			else pos+=t->lc->size+1,t=t->rc;
		}
		pushdown(t);//这个pushdown不能省
		pos+=t->lc->size;
		//那个+1已经由空节点加过了
		printf("%d ",pos+k-1);//前面已经摞了k-1个
		select(Root,1);//将左哨兵放到根
		select(Root->rc,pos+1);//将最小值后面的点放在根的右儿子
		select(Root->rc->lc,pos);//将最小值放在根右儿子的左儿子,这样它的子树就是从第一个点开始
		Root->rc->lc->rev^=1;
		pushdown(Root->rc->lc);//翻转从第一个点开始的一段
		select(Root->rc,2);//将翻转后的第二个点提到根的右儿子,从而把最小值单独"撇"到其左儿子
		delete Root->rc->lc;//删除这个最小值
		Root->rc->lc=Nil;
		splay(Root,Root->rc);//更新之
	}
}tree;
int N;
pair<int,int> height[SIZEN];
int equh[SIZEN]={0};//处理顺序,即等效高度
bool work(void){
	scanf("%d",&N);
	if(!N) return false;
	for(int i=1;i<=N;i++) scanf("%d",&height[i].first),height[i].second=i;
	sort(height+1,height+1+N);
	for(int i=1;i<=N;i++) equh[height[i].second]=i;
	tree.clear();
	tree.insert(equh,N);
	for(int i=1;i<=N;i++) tree.findmin(i);
	printf("\n");
	return true;
}
int main(){
	freopen("roboticsort.in","r",stdin);
	freopen("roboticsort.out","w",stdout);
	while(work());
	return 0;
}