有关平衡树的问题很多时候其实是可以用树状数组或是set来处理的，但似乎题解很少有这方面的说明赶紧水一发
本题值域范围不大，所以可以之间在线做，但一般开到$10^9$，这时候就需要离散化三连sort,unique,lower_bound，在离散化之后树状数组用来维护值域
首先对于操作1，直接在x对应的位置+1就好了，操作2同理
操作3只要查询x-1的前缀和就是比x的小的所有的数，+1就是排名了
操作4就是找到前缀和中第一个大于等于x的对应的数，因为前缀和其实就是排名
操作5和6同理，5中比如比x小的有k个数，我只要正好找到前缀和中第一个大于等于k对应的数就好了，需要注意的是两个操作的实现有一些不同
1
2
|
if(p[i]==5) printf("%d\n",query(sum(hash(a[i])-1)));
if(p[i]==6) printf("%d\n",query(sum(hash(a[i]))+1));
|
为什么查询前驱
从$sum(i-1)$里找而后继要从$sum(i)+1$而不是$sum(i+1)$里找呢，这是因为我们为了离散化方便把查询排名的x也插了进去，这个地方可能是没有数的，$sum(i+1)$就和$sum(i)$一样了，所以这样处理
而如何查询第一个前缀和大于等于x对应的数呢，这里有两种方法，一种就是二分，还有一种就是通过树状数组的性质来处理，二分似乎之前有一篇题解提到过，这里介绍第二种方法
首先树状数组其实是一颗二叉树，让我们看这幅图
图片来源网络
我们发现二的幂次方维护的值从开头开始的，假设我们现在在8这个点，维护的是8的前缀和，但这个值已经比k大了，不满足最小，所以我们跳到4，其实就相当于往左儿子走，假如5是符合要求的，那我们从4跳到6(+$2^1$)发现不可以，再跳到5($+2^0$)发现可以，之后返回，所以时间复杂度是和$logn$有关的，总以通过
接下来是代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
#include<bits/stdc++.h>
using namespace std;
const int maxn=100050;
inline int read()
{
int x=0,t=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')t=-1;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x*t;
}
int n,q[maxn],a[maxn],p[maxn],tot=0,c[maxn];
int hash(int x){return lower_bound(q+1,q+1+tot,x)-q;}
int lowbit(int x){return x&-x;}
void add(int x,int p)
{
while(x<=tot)
{
c[x]+=p;
x+=lowbit(x);
}
}
int sum(int x)
{
int res=0;
while(x)
{
res+=c[x];
x-=lowbit(x);
}
return res;
}
int query(int x)
{
int t=0;
for(int i=19;i>=0;i--)
{
t+=1<<i;
if(t>tot||c[t]>=x) t-=1<<i;
else x-=c[t];
}
return q[t+1];
}
int main()
{
n=read();
for(int i=1;i<=n;i++)
{
p[i]=read(),a[i]=read();
if(p[i]!=4) q[++tot]=a[i];
}
//hash
sort(q+1,q+1+tot);
tot=unique(q+1,q+1+tot)-(1+q);
for(int i=1;i<=n;i++)
{
if(p[i]==1) add(hash(a[i]),1);
if(p[i]==2) add(hash(a[i]),-1);
if(p[i]==3) printf("%d\n",sum(hash(a[i])-1)+1);
if(p[i]==4) printf("%d\n",query(a[i]));
if(p[i]==5) printf("%d\n",query(sum(hash(a[i])-1)));
if(p[i]==6) printf("%d\n",query(sum(hash(a[i]))+1));
}
return 0;
}
|