平衡树

#include<bits/stdc++.h>
using namespace std;
int cnt=1;
struct tree{
	int num,left,head,right,t;
};
tree a[10000];
void find(int p,int q){
	if(a[p].num>=a[q].num){
		if(a[p].left==0){
			a[p].left=q;
			a[q].head=p;
		}
		else find(a[p].left,q);
		if(a[p].t>a[a[p].left].t){
			a[a[p].left].head=a[p].head;
			if(a[a[p].head].left==p) a[a[p].head].left=a[p].left;
			else a[a[p].head].right=a[p].left;
			a[p].head=a[p].left;
			a[p].left=a[a[p].head].right;
			a[a[p].head].right=p;
		}
	}
	else{
		if(a[p].right==0){
			a[p].right=q;
			a[q].head=p;
		}
		else find(a[p].right,q);
		if(a[p].t>a[a[p].right].t){
			a[a[p].right].head=a[p].head;
			if(a[a[p].head].left==p) a[a[p].head].left=a[p].right;
			else a[a[p].head].right=a[p].right;
			a[p].head=a[p].right;
			a[p].right=a[a[p].head].left;
			a[a[p].head].left=p;
		}
	}
	
}
void prt(int p){
	if(a[p].left>0) prt(a[p].left);
	cout<<a[p].num<<" ";
	if(a[p].right>0) prt(a[p].right);
}
int main(){
	int n,h,i,j,k;
	cin>>n>>h;
	a[1].head=1;
	a[1].num=h;
	a[cnt].left=0;
	a[cnt].right=0;
	a[cnt].t=-1;
	for(i=1;i<n;i++){
		cnt++;
		cin>>a[cnt].num;
		a[cnt].left=0;
	    a[cnt].right=0;
	    a[cnt].t=rand()%1000;
		find(1,cnt);
	}
	prt(1);
}