维护当前节点代表值出现的次数。

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

1。插入x数
2。删除x数(若有多个相同的数，因只删除一个)
3。查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名)
4。查询排名为x的数
5。求x的前驱(前驱定义为小于x，且最大的数)
6。求x的后继(后继定义为大于x，且最小的数)
输入格式
第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号( 1≤opt≤6 )

输出格式
对于操作3,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≤100000

2.每个数的数据范围： [-{10}^7 , {10}^7]
来源：Tyvj1728 原名：普通平衡树

在此鸣谢

权值线段树搞搞就好啦。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<queue>
#define ll long long
#define llu unsigned ll
using namespace std;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const int maxn=100100;
int id[maxn],a[maxn],b[maxn];
struct node
{
    int l,r;
    int sum;
}t[maxn<<2];

void pushup(int cnt)
{
    t[cnt].sum=t[cnt<<1].sum+t[cnt<<1|1].sum;
}

void build(int l,int r,int cnt)
{
    t[cnt].l=l,t[cnt].r=r;
    t[cnt].sum=0;
    if(l==r) return ;
    int mid=(l+r)>>1;
    build(l,mid,cnt<<1);
    build(mid+1,r,cnt<<1|1);
}

void change12(int pos,int val,int cnt)
{
    if(t[cnt].l==t[cnt].r)
    {
        t[cnt].sum+=val;
        if(t[cnt].sum<0) t[cnt].sum=0;
        return ;
    }
    if(pos<=t[cnt<<1].r) change12(pos,val,cnt<<1);
    else change12(pos,val,cnt<<1|1);
    pushup(cnt);
}

int ask3(int l,int r,int cnt)
{
    if(l>r) return 0;
    if(l<=t[cnt].l&&t[cnt].r<=r)
    {
        return t[cnt].sum;
    }
    int ans=0;
    if(l<=t[cnt<<1].r) ans+=ask3(l,r,cnt<<1);
    if(r>=t[cnt<<1|1].l) ans+=ask3(l,r,cnt<<1|1);
    return ans;
}

int ask4(int val,int cnt)
{
    if(t[cnt].sum<val) return 0;
    if(t[cnt].l==t[cnt].r)
    {
        return t[cnt].l;
    }
    if(val<=t[cnt<<1].sum) return ask4(val,cnt<<1);
    else return ask4(val-t[cnt<<1].sum,cnt<<1|1);
}

int ask5(int pos)
{
    int ans=ask3(1,pos-1,1);
    return ask4(ans,1);
}

int ask6(int pos)
{
    int ans=ask3(1,pos,1);
    return ask4(ans+1,1);
}

int main(void)
{
    int n;
    scanf("%d",&n);
    int pt=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&id[i],&a[i]);
        if(id[i]!=4) b[++pt]=a[i];
    }

    sort(b+1,b+pt+1);
    int cnt=unique(b+1,b+pt+1)-(b+1);

    build(1,cnt,1);

    for(int i=1;i<=n;i++)
        if(id[i]!=4)a[i]=lower_bound(b+1,b+cnt+1,a[i])-b;

    for(int i=1;i<=n;i++)
    {
        if(id[i]==1)
            change12(a[i],1,1);
        else if(id[i]==2)
            change12(a[i],-1,1);
        else if(id[i]==3)
            printf("%d\n",ask3(1,a[i]-1,1)+1);
        else if(id[i]==4)
            printf("%d\n",b[ask4(a[i],1)]);
        else if(id[i]==5)
            printf("%d\n",b[ask5(a[i])]);
        else if(id[i]==6)
            printf("%d\n",b[ask6(a[i])]);
    }
    return 0;
}