Treap树堆非旋转算法

核心操作：分裂与合并
1.分裂(split)有两种：按权值分裂与按位置(排名)分裂
如果按权值分裂(split):那么分出来两棵树的第一棵树上的每个数的大小都小于(或者小于等于，视具体情况)x。
如果按位置分裂(split):那么分出来两棵树的第一棵树上恰好有x个结点。

//按权值分裂
inline void split(int k,int &l,int &r,int x)
{//将以k为根的树按权值x分成两棵树分别以l为根(小于x)，以r为根(不小于x)
      if(!k){//分裂到底了，返回
           l=r=0;
           return ;
      }
      if(tree[k].val

 2.合并操作

inline void merge(int &k,int l,int r)
{//以l为根的树(权值小于以r为根的权值）和以r为根的树合并到以k为根的树
      if(!l||!r){
           k=l+r;
           return ;
       }
       if(tree[l].p>tree[r].p){//默认为大根堆
           k=l;
           merge(tree[k].r,tree[k].r,r);
      else{
           k=r;
           merge(tree[k].l,l,tree[k].l);
      }
      push_up(k);
}


3.插入操作

inline void insert(int val){
      int x,y;
      split(root,x,y,val);//按val分裂后x树的值小于val，y树的值不小于val
      merge(x,x,New(val));
      merge(root,x,y);
}


4.删除操作

inline void Delete(int val){
         int x,y,z;
         split(root,x,y,val+1);
         split(x,x,z,val);
         merge(z,tree[z].l,tree[z].r);
         merge(x,x,z);
         merge(root,x,y);
}


5.x的排名

inline int rnk(int val){
         int x,y;
         split(root,x,y,val);
         int ans=tree[x].size+1;
         merge(root,x,y);
         return ans;
}


 6.x的前驱

inline int pre(int val){
         int x,y;
         split(root,x,y,val);
         int z;
         z=x;
         while(tree[z].r!=0)  z=tree[z].r;//x树中的最大值
         int ans=tree[z].val;
         merge(root,x,y);
         return ans;
}


7.x的后续

inline int suf(int val){
         int x,y;
         split(root,x,y,val+1);
         int z;
         z=y;
         while(tree[z].l!=0) z=tree[z].l;//y树的最小值
         int ans=tree[z].val;    
         merge(root,x,y);
         return ans;
}


8.更新

inline  void push_up(int k){
           tree[k].size=tree[tree[k].l].size+tree[tree[k].r].size+1;
}


9.新建结点

inline int New(int val){
         tree[++cnt].val=val;
         tree[cnt].l=tree[cnt].r=0;
         tree[cnt].size=1;
         return cnt;
}


10.数据类型

const int maxn=100010;
struct node{
          int val;
          int p;
          int size;
          int l;
          int r;
} tree[maxn];
int cnt,root;


 P3369 【模板】普通平衡树



//非旋转 数组版 
#include
using namespace std;
const int maxn=1000000;
struct node{
	int val;
	int size;
	int p;
	int l;
	int r;
}tree[maxn]; 
int root,cnt;
inline void push_up(int k)
{
	tree[k].size=tree[tree[k].l].size+tree[tree[k].r].size+1;
}
inline void split(int k,int &l,int &r,int x)
{
	if (!k)
	{
		l=r=0;
		return ;
	}
	if (tree[k].valtree[r].p)
	{
		k=l;
		merge(tree[k].r,tree[k].r,r);
	}
	else
	{
		k=r;
		merge(tree[k].l,l,tree[k].l);
	}
	push_up(k);
}
int New(int val)
{
	tree[++cnt].val=val;
	tree[cnt].r=tree[cnt].l=0;
	tree[cnt].size=1;
	tree[cnt].p=rand();
	return cnt;
}
inline void insert(int val)
{
	int x,y;
	split(root,x,y,val);
	merge(x,x,New(val));
	merge(root,x,y);
} 
inline void Delete(int val)
{
	int x,y,z;
	split(root,x,y,val+1);
	split(x,x,z,val);
	merge(z,tree[z].l,tree[z].r);
	merge(x,x,z);
	merge(root,x,y);
}
inline int rnk(int val)
{
	int x,y;
	split(root,x,y,val);
	int ans=tree[x].size+1;
	merge(root,x,y);
	return ans;
}
inline int kth(int k)
{
	int x=root;
	while(true)
	{
		if (k==tree[tree[x].l].size+1) return tree[x].val;
		if (k<=tree[tree[x].l].size) x=tree[x].l;
		else 
		{
			k-=tree[tree[x].l].size+1;
			x=tree[x].r;
		}
	}
}
inline int pre(int val)
{
	int x,y,z;
	split(root,x,y,val);
	z=x;
	while(tree[z].r!=0)
	{
		z=tree[z].r;
	}
	int ans=tree[z].val;
	merge(root,x,y);
	return ans;
}
inline int suf(int val)
{
	int x,y;
	split(root,x,y,val+1);
	int z;
	z=y;
	while(tree[z].l!=0)
	{
		z=tree[z].l;
	}
	int ans=tree[z].val;
	merge(root,x,y);
	return ans;
}
int main()
{
	int n;
	cin>>n;
	while(n--)
	{
		int op,x;
		cin>>op;
		if (op==1)
		{
			cin>>x;
			insert(x);
		}
		else if(op==2)
		{
			cin>>x;
			Delete(x);
		}
		else if(op==3)
		{
			cin>>x;
			cout<>x;
			cout<>x;
			cout<>x;
			cout<