luogu P3369 【模板】普通平衡树

题目描述

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

插入 xxx 数
删除 xxx 数(若有多个相同的数，因只删除一个)
查询 xxx 数的排名(排名定义为比当前数小的数的个数 +1+1+1 )
查询排名为 xxx 的数
求 xxx 的前驱(前驱定义为小于 xxx，且最大的数)
求 xxx 的后继(后继定义为大于 xxx，且最小的数)

输入格式

第一行为 nnn，表示操作的个数,下面 nnn 行每行有两个数 opt\text{opt}opt 和 xxx，opt\text{opt}opt 表示操作的序号( 1≤opt≤6 1 \leq \text{opt} \leq 6 1≤opt≤6 )

输出格式

对于操作 3,4,5,63,4,5,63,4,5,6 每行输出一个数，表示对应答案

#include<bits/stdc++.h>
#define maxn (100000+500)
#define inf 2000000005
using namespace std;
int sum=0,R=0;
int size[maxn],v[maxn],num[maxn],rd[maxn],son[maxn][2];
inline void pushup(int p){ size[p]=size[son[p][0]]+size[son[p][1]]+num[p]; }
inline void rotate(int &p,int d){ //旋转
    int k=son[p][d^1];
    son[p][d^1]=son[k][d];
    son[k][d]=p;
    pushup(p);
    pushup(k);
    p=k;
}
inline void ins(int &p,int x){
    if (!p){//空节点
        p=++sum;
        size[p]=num[p]=1;
        v[p]=x;
        rd[p]=rand();
        return;
    }
    if (v[p]==x){//相等
        num[p]++;
        size[p]++;
        return;
    }
    int d=(x>v[p]);//判断左右子树
    ins(son[p][d],x);//插入
    if (rd[p]<rd[son[p][d]]) rotate(p,d^1); //不满足就旋转
    pushup(p);//更新size
}
inline void del(int &p,int x){
    if (!p) return;//空节点
    if (x<v[p]) del(son[p][0],x); //在左子树
    else if (x>v[p]) del(son[p][1],x);//在右子树
    else{
        if (!son[p][0] && !son[p][1]){//没有子树
            num[p]--; size[p]--; 
            if (num[p]==0) p=0;
        } 
        else if (son[p][0] && !son[p][1]){//有右字树
            rotate(p,1);
            del(son[p][1],x);
        }
        else if (!son[p][0] && son[p][1]){//有左子树
            rotate(p,0);
            del(son[p][0],x);
        }
        else if (son[p][0] && son[p][1]){//都存在
            int d=(rd[son[p][0]]>rd[son[p][1]]);
            rotate(p,d);
            del(son[p][d],x);
        }
    }
    pushup(p);
}
inline int rank(int p,int x){
    if (!p) return 0;
    if (v[p]==x) return size[son[p][0]]+1;
    if (v[p]<x) return size[son[p][0]]+num[p]+rank(son[p][1],x);
    if (v[p]>x) return rank(son[p][0],x);
}
inline int find(int p,int x){
    if (!p) return 0;
    if (size[son[p][0]]>=x) return find(son[p][0],x);
    else if (size[son[p][0]]+num[p]<x)
        return find(son[p][1],x-num[p]-size[son[p][0]]);
    else return v[p];
}
inline int pre(int p,int x){
    if (!p) return -inf;
    if (v[p]>=x) return pre(son[p][0],x);
    else return max(v[p],pre(son[p][1],x));
}
int suc(int p,int x){
    if (!p) return inf;
    if (v[p]<=x) return suc(son[p][1],x);
    else return min(v[p],suc(son[p][0],x));
}

int main(){
    int n;
    scanf("%d",&n);
    for (int i=0;i<n;++i){
        int opt,x;
        scanf("%d%d",&opt,&x);
        if (opt==1) ins(R,x);
        else if (opt==2) del(R,x);
        else if (opt==3) printf("%d\n",rank(R,x));
        else if (opt==4) printf("%d\n",find(R,x));
        else if (opt==5) printf("%d\n",pre(R,x));
        else if (opt==6) printf("%d\n",suc(R,x));
    }
}

luogu P3369 【模板】普通平衡树

原文：https://www.cnblogs.com/naruto-mzx/p/12134772.html