Splay树、Treap树

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=101000;
const int INF=0x3fffffff;
typedef long long LL;
//建树：
//用Splay旋转到根，其左子树的大小即排在左边的个数 ，输出就可以
//翻转左子树：用了线段树的思想：进行标记，而不是直接操作，等splay操作的时候在处理
//标记函数：updat_rev(),
//删除根：根据标记进行子树的翻转 
int rev[maxn]; //标记i被翻转
int pre[maxn]; //i的父节点
int size[maxn];  //i的子树上节点的个数
int tree[maxn][2] ; //记录树，0左，1右
int root;
struct node{
	int val,id;
	bool operator < (const node &a)const{
		if(val==a.val) return id<a.id;
		else return val<a.val;
	}
}nodes[maxn]; 

void push_up(int x){   //记录以x为根的子树包含的节点 
	size[x]=size[tree[x][0]]+size[tree[x][1]]+1;
}
//进行旋转 
void updata_rev(int x){
	if(!x) return; //NULL
	swap(tree[x][0],tree[x][1]);
	rev[x]^=1;   //记录已经更新了 
}
void pushdown(int x){
	if(rev[x]){   //如果标记了，就旋转，一般用在 rotate和splay 
		updata_rev(tree[x][0]); 
		updata_rev(tree[x][1]);
		rev[x]=0;
	}
}
void Rotate(int x,int c){  //c=0左旋， c=1右旋 
	int y=pre[x];
	pushdown(y);
	pushdown(x);    //先更新 
	//然后就是更改和更新信息
	//1、改变父子结构
	tree[y][!c]=tree[x][c];   //y的儿子 
	pre[tree[x][c]]=y;        //x的儿子重新认爸爸
	if(pre[y]){
		tree[pre[y]][tree[pre[y]][1]==y]=x;  //改变儿子，y的爸爸
		                //原来是哪边，现在还是哪边 
	} 
	pre[x]=pre[y]; //x也重新仁爸爸 
	tree[x][c]=y;  //儿子
	pre[y]=x;
	push_up(y); 
}
void splay(int x,int goal){  //把节点x作为goal的孩子，如果goal为0，那么就是旋转到跟
	pushdown(x); 
 	while(pre[x]!=goal){  //一直旋转，知道成为goal的孩子
	 //区分三种情况
	 if(pre[pre[x]]==goal){  //1、父节点是根，直接旋转一次就可以
	 	pushdown(pre[x]);
	 	pushdown(x); 
	 	Rotate(x,tree[pre[x]][0]==x); //左孩子：右旋，右孩子：左旋 
	 } 
	 else{  //父节点不是根 
	 	pushdown(pre[pre[x]]);
	 	pushdown(pre[x]);  //先更新 
	 	pushdown(x);
	 	int y=pre[x];
	 	int c=(tree[pre[y]][0]==y);  //先判断父节点是左还是右孩子
		if(tree[y][c]==x){  //三点不共线！！！！  把x按不同的方向旋转2次
			Rotate(x,!c);
			Rotate(x,c);
		} 
		else{  //三点共线 先旋转x的父节点，在旋转x
			Rotate(y,c);  
			Rotate(x,c);
		}
	 }
}
	 push_up(x);
	 if(goal==0) root=x; //如果goal是0，那么就更新根节点 
} 

//接下来是删除节点操作
int get_max(int x){
	pushdown(x);  //更新
	while(tree[x][1]) {
		x=tree[x][1];     //找前驱：一直在做孩子的右节点找：BST 
		pushdown(x);  
	}
	return x;
} 

void del_node(){
	//删除根节点（通过前面的操作，已经把需要删除的节点放在根节点了 
	if(tree[root][0]==0){ //没有左孩子：没有前驱，而且可以直接删掉 
		root=tree[root][1];
		pre[root]=0;
	}
	else{
		int m=get_max(tree[root][0]);  //找到前驱
		splay(m,root);  //提根
		tree[m][1]=tree[root][1];  //右孩子=另一棵树（相当于合并两棵树
		pre[tree[root][1]]=m; //更新爸爸
		root=m; 
		pre[root]=0;
		push_up(root);
	}
}
void newnode(int &x,int fa,int val){  //新建节点
	x=val;
	pre[x]=fa;
	size[x]=1;
	rev[x]=0;
	tree[x][0]=tree[x][1]=0;  //全体初始化 
}
void buildtree(int &x,int l,int r,int fa){  //建树 
	if(l>r) return;
	int mid=(l+r)>>1; //中间开始建（平衡）
	newnode(x,fa,mid);  //先按照初始位置建树！！！
	buildtree(tree[x][0],l,mid-1,x);
	buildtree(tree[x][1],mid+1,r,x);
	push_up(x); 
}
void inti(int n){
	root=0;
	tree[root][0]=tree[root][1]=pre[root]=size[root]=0;
	buildtree(root,1,n,0);
}

int main(){
	int n;
	while(~scanf("%d",&n)&&n){
		inti(n);
		for(int i=1;i<=n;i++){
			scanf("%d",&nodes[i].val);
			nodes[i].id=i;
		}
		sort(nodes+1,nodes+1+n);
		for(int i=1;i<n;i++){  //只进行n-1次操作 
			splay(nodes[i].id,0);   //第i次旋转：把第i大的节点旋转到根 
			updata_rev(tree[root][0]); //左子树需要旋转
			printf("%d ",i+size[tree[root][0]]);  
			//第i个被翻转的数的左边的数，就是左子树的个数
			del_node(); 
		}
		printf("%d\n",n);
	}
return 0;
}