P3369 【模板】普通平衡树

1.插入 xx 数

2.删除 xx 数(若有多个相同的数，因只删除一个)

3.查询 xx 数的排名(排名定义为比当前数小的数的个数 +1+1 )

4.查询排名为 xx 的数

5.求 xx 的前驱(前驱定义为小于 xx，且最大的数)

6.求 xx 的后继(后继定义为大于 xx，且最小的数

10

1 106465

4 1

1 317721

1 460929

1 644985

1 84185

1 89851

6 81968

1 492737

5 493598

第一个4输出的是0

输入第五个1后就输入不了了（qwq）

蒟蒻的程序如下

#include<bits/stdc++.h>
using namespace std;
const int most=100001; 
int tot=0,root=1;
struct t{
int lc,rc,wv,pri,cnt,size,fa,vis;
#define lc(x) t[x].lc//左儿子 (储存指针)
#define rc(x) t[x].rc//右儿子 (储存指针)
#define fa(x) t[x].fa//父结点 (储存指针)
#define v(x) t[x].wv//权值 
#define p(x) t[x].pri//优先级 
#define c(x) t[x].cnt//桶 
#define s(x) t[x].size//子树节点数 
} t[most];
inline void check(int &x,int &y)//更换父节点连线 
{
	 if(fa(x))
     {
     	if(lc(fa(x))==x) lc(fa(x))=y;
	     else rc(fa(x))=y;
	 }
}
inline void rt(int &x)//右旋 
{
     int y=lc(x),w=s(y);
     if(root==x) root=y;//更新根结点 
     lc(x)=rc(y);rc(y)=x;//换结点
     s(y)=s(x);//更换子树节点数
	 s(x)=s(lc(x))+s(rc(x))+c(x); 
     check(x,y);
	 x=y;
	 return;
}
//
inline void lt(int &x)//左旋 
{
     int y=rc(x),w=s(y); 
     if(root==x) root=y;//更新根结点 
     rc(x)=lc(y);lc(y)=x;//换结点 
     s(y)=s(x);//更换节点数（包括下一行） 
     s(x)=s(lc(x))+s(rc(x))+c(x);
    check(x,y);
     x=y;
     return;
}
//
inline void ad(int &x,int y){//新增节点，
	 v(x=++tot)=y;//点权 
     p(x)=rand();//随机优先级
     s(x)=1;//目前是新建叶子节点，所以子树大小为1
     c(x)=1;//新建同节点为1(桶)
     lc(x)=rc(x)=0;
    return;
}
//
void  put(int &x,const int vi)//插入 
{
     if(!x)
     { ad(x,vi);
	 return; }//添加节点 
     ++s(x);
     if(vi==v(x))
      c(x)++; 
     else if(vi<v(x))
    {
      put(lc(x),vi);
      if(p(lc(x))<p(x))//符合条件->右旋 
 	    rt(x);
    }
    else
   {
    put(rc(x),vi);
    if(p(rc(x))<p(x))//符合条件->左旋 
      lt(x);
    }
    return; 
}
//
void dlt(int &k,const int key)//删除节点 
{
     --s(k);
	if(v(k)==key)
	{
		if(c(k)>1)
		  --c(k);//有重复元素 
		else if(!lc(k) || !rc(k))    //链或空 
		 {
		    if(root==k)
		 	root=lc(k)+rc(k);
		 	k=lc(k)+rc(k);
		 }
		else if(p(lc(k))<p(rc(k)))//维护堆 
		 rt(k);
		else if(p(lc(k))>p(rc(k)))
		 lt(k);
		return;
	 } 
	 if(key<v(k)) dlt(lc(k),key);
	 else dlt(rc(k),key);
	 return;
}
// 
int hp(const int key)//前驱 (前驱定义为小于x，且最大的数)
{
	int x=root,ans=0;
	while(x)
	{
		if(v(x)<=key)
		{ ans=v(x),x=rc(x); }
		else
		x=lc(x);
	}
	return ans;
 } 
//
int bp(const int key)//后继(后继定义为大于x,且最小的数)
{
	int x=root,ans=-99999;
	while(x)
	{
		if(v(x)>key) ans=v(x),x=lc(x);
		else
		x=rc(x);
	}
 } 
//
int shfind(int k)//排名 (第k位的数)
{
	int x=root;
	while(x)
	{
		if(s(lc(x))<k and s(lc(x))+c(x)>=k)
		 return v(x);
		if(s(lc(x))>k)
		 x=lc(x);
		else
		{
			k-=s(lc(x))+c(x);
			x=rc(x);
		}
	}
	return 0;
}
//
int  rank(const int k)//排名 （x的名次） 
{
	int x=root,ans=0;
	while(x)
	{
		if(k==v(x)) return ans+s(lc(x))+1;
		if(k<s(lc(x))) x=lc(x);
		else
		ans+=s(lc(x))+c(x),x=rc(x);
	 } 
	 return 0;
 } 
//
int main()
{
	int n,x,k;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d",&x,&k);
		if(x==1) 
		put(root,k);
		if(x==2) 
			dlt(root,k);
		if(x==3)
			printf("%d\n",rank(k));
		if(x==4) 
			printf("%d\n",shfind(k));
		if(x==5)
			printf("%d\n",hp(k));
		if(x==6) 
			printf("%d\n",bp(k));
	}
	return 0;
}