P3369 【模板】普通平衡树 01Trie树

P3369 【模板】普通平衡树

题目描述

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

1. 插入xx数
2. 删除xx数(若有多个相同的数，因只删除一个)
3. 查询xx数的排名(排名定义为比当前数小的数的个数+1+1。若有多个相同的数，因输出最小的排名)
4. 查询排名为xx的数
5. 求xx的前驱(前驱定义为小于xx，且最大的数)
6. 求xx的后继(后继定义为大于xx，且最小的数)

输入格式

第一行为nn，表示操作的个数,下面nn行每行有两个数optopt和xx，optopt表示操作的序号( 1 leq opt leq 61≤opt≤6 )

输出格式

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

输入输出样例

输入 #1复制

10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

输出 #1复制

106465
84185
492737

说明/提示

时空限制：1000ms,128M

1.n的数据范围： n leq 100000n≤100000

2.每个数的数据范围： [-{10}^7, {10}^7][−107,107]

来源：Tyvj1728 原名：普通平衡树

在此鸣谢

#include<bits/stdc++.h>
#define inf 1e7
using namespace std;
const int maxn=100005,maxm=maxn*20,N=24;//2^20 
int ch[maxm][2],v[maxm];
int cnt=1;
void Add(int pos,int qx)
{
    pos+=inf;//防止负数 
    int p=1;//把0号节点空出来 
    for(int i=N;i>=0;i--)
    {
        bool b=(pos>>i)&1;//判断是不是1
        if(!ch[p][b])
            ch[p][b]=++cnt;//动态开点 
        v[p]+=qx;
        p=ch[p][b]; 
    }
    v[p]+=qx;//叶子结点还没有修改 
}
int Sum(int pos)
{
    pos+=inf+1;//+1就是小于等于了 
    int res=0,p=1;
    for(int i=N;i>=0;i--)
    {
        bool b=(pos>>i)&1;
        if(b)// right
            res+=v[ch[p][0]];
        p=ch[p][b];
        if(!p)
            break;
    }
    return res;
}
int Get(int rank)
{
    int p=1,res=0;
    for(int i=N;i>=0;i--)
    {
        if(v[ch[p][0]]>=rank)
            p=ch[p][0];
        else
            rank-=v[ch[p][0]],p=ch[p][1],res|=1<<i;
    }
    return res-inf;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int opt,x;
        scanf("%d%d",&opt,&x);
        if(opt==1)
        {
            Add(x,1);
        }
        if(opt==2)
        {
            Add(x,-1);
        }
        if(opt==3)
        {
            printf("%d
",Sum(x-1)+1);
        }
        if(opt==4)
        {
            printf("%d
",Get(x));
        }
        if(opt==5)
        {
            int tmp=Sum(x-1)+1;//rank x 
            printf("%d
",Get(tmp-1));
        }
        if(opt==6)
        {
            int tmp=Sum(x)+1;//rank x+1
            printf("%d
",Get(tmp)); 
        }
    }
    
    
    return 0;
}

把数字转化为二进制（当做字符串）存在Trie树上 这类似权值线段树 一个二分的思想