codeforces 38G Queue splay

題意：有n個人依次排隊，每個人都有兩個屬性值a[ i ]、c[ i ]，a[ i ]是重要性值，數值越大越重要，c[ i ]是良心值。假如第i個人來是排

隊，初始時他在隊尾，如果他的a[ i ]大于排在他前面那位的重要性值，那麼兩人可以交換位置，每次交換良心值減1，直到他前面的

人的重要性值大于a[ i ]或者良心值為0的時候，問最終n個人的隊列次序。

思路：splay的val存重要性值，Max維護目前子樹的最大值。假設目前要插入的人的重要性值為val，我們遞歸插入。當遞歸到以x為

根的子樹時，設此時這人目前的良心值為sz, 那麼如果val < x->ch[ 1 ]->Max 或者 val < x->val 或者 sz <= x->ch[1]->s（右子樹的結點

個數）時，隻能往右子樹遞歸插入，不然往左子樹插入。插入完成後，将其旋轉至根。因為splay中維護的val是重要性值，而最後輸

出的是排第幾個位置的是第幾個人，是以需要将val值映射一下，詳見代碼：

// file name: codeforces38G.cpp //
// author: kereo //
// create time:  2014年08月26日 星期二 08時40分02秒 //
//***********************************//
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=100000+100;
const int inf=0x3fffffff;
#define L(x) (x<<1)
#define R(x) (x<<1|1)
int n,top,cnt;
int st[MAXN];
struct node
{
	int s,val,Max;
	node *fa,*ch[2];
}nod[MAXN],nil,*null,*root;
map<int,int>mp;
struct Splay
{
	void init(){
		cnt=top=0;
		nil.s=nil.val=nil.Max=0; null=&nil;
		newnode(root,null,inf); //最左端
		newnode(root->ch[1],root,-1); //最右端
		push_up(root);
	}
	void newnode(node *&x,node *f,int val){ //這也一定要用引用,因為你傳入的本質是位址常數，而本身你想修改這個數，是以必須要用引用
		if(top) x=&nod[st[--top]];
		else x=&nod[cnt++];
		x->s=1; x->val=x->Max=val; x->fa=f; x->ch[0]=x->ch[1]=null;
	}
	void push_up(node *x){
		x->s=1; x->Max=x->val;
		if(x->ch[0]!=null) x->s+=x->ch[0]->s, x->Max=max(x->Max,x->ch[0]->Max);	
		if(x->ch[1]!=null) x->s+=x->ch[1]->s, x->Max=max(x->Max,x->ch[1]->Max);
	}
	void rotate(node *x,int d){
		node *y=x->fa; //保證y不為null
		//push_down(y); push_down(x);
		y->ch[d^1]=x->ch[d];
		if(x->ch[d]!=null) x->ch[d]->fa=y;
		x->fa=y->fa;
		if(y->fa!=null){
			int d1=y->fa->ch[0] == y ? 0 : 1;
			y->fa->ch[d1]=x;
		}
		x->ch[d]=y; y->fa=x;
		push_up(y);
	}
	void splay(node *x,node *f){
		//push_down(x);
		while(x->fa!=f){
			node *y=x->fa;
			if(y->fa == f){
				int d=y->ch[0] == x ? 1 : 0;
				rotate(x,d);
			}
			else{
				int d=y->fa->ch[0] == y ? 1 : 0;
				if(y->ch[d] == x){ //之字型
					rotate(x,d^1); rotate(x,d);
				}
				else{//一字型
					rotate(y,d); rotate(x,d);
				}
			}
		}
		push_up(x);
		if(f == null) root=x;
	}
	void insert(node *&x,node *f,int val,int sz){ //考慮能否插到x之前
		if(x == null){
			newnode(x,f,val);
			return ;
		}
		if(val<x->ch[1]->Max || val<x->val || sz<x->ch[1]->s) //注意是sz<x->ch[1]->s，因為裡面有一個自己設的R(root)結點
			insert(x->ch[1],x,val,sz);
		else 
			insert(x->ch[0],x,val,sz-x->ch[1]->s-1);
		push_up(x);
	}
}spt;
void dfs(node *x){
	if(x->ch[0]!=null)
		dfs(x->ch[0]);
	if(x->val!=-1 && x->val!=inf)
		printf("%d ",mp[x->val]);
	if(x->ch[1]!=null)
		dfs(x->ch[1]);
}
int main()
{
	while(~scanf("%d",&n)){
		mp.clear(); spt.init();
		for(int i=1;i<=n;i++){
			int a,c;
			scanf("%d%d",&a,&c);
			spt.insert(root,null,a,c);
			spt.splay(&nod[cnt-1],null);
			mp[a]=i;
		}
		dfs(root);
		printf("\n");
	}
	return 0;
}