引入
权值树状数组就是数组下标是数值的数组，数组存储下标对应的值有几个数
题目 HDU-2852 KiKi's K-Number
题意
几种操作，p=0代表push：将数值为a的数压入盒子
p=1代表pop，代表删除数值为e的数，如果没有这个数，输出No Elment!
p=2代表query，查询比第k个比a大的元素，找不到输出Not Find!
Sample Input
5
0 5
1 2
0 6
2 3 2
2 8 1
7
0 2
0 2
0 4
2 1 1
2 1 2
2 1 3
2 1 4
Sample Output
No Elment!
6
Not Find!
2
2
4
Not Find!
题解
此题正是权值树状数组的应用，插入和删除都比较简单不再赘述了，重点是查询怎么查询，我们的树状数组是存储的对应权值的个数。我们在查询的时候，首先查询出a是第(x)大的元素，那么查询比a大k的元素就转化为查询第(x+k)大的元素，然后我们二分查找，判断当前的数是第几大的数，多了就向小二分，但要注意判断，如果当前找到的是第(res)大的数，vis[mid]代表这个数有多少个，如果(res-vis[mid] < k 且res >= k)说明mid就是要找的数
AC代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100005
using namespace std;
typedef long long ll;
int lowbit(int x) {
return x & (-x);
}
int min(int a, int b) {return a < b ? a : b; }
int max(int a, int b) {return a > b ? a : b; }
int m;
int d[N + 5];
void update(int x, int val) {
for (; x <= N; x += lowbit(x))
d[x] += val;
}
int query(int x) {
int ans = 0;
for (; x; x -= lowbit(x))
ans += d[x];
return ans;
}
int vis[N];
int main() {
while (scanf("%d", &m) != EOF) {
memset(d, 0, sizeof(d));
memset(vis, 0, sizeof(vis));
for (int i = 1; i <= m; i++) {
int p, x;
scanf("%d", &p);
if (p == 0) {
scanf("%d", &x);
vis[x]++;
update(x, 1);
}
else if (p == 1) {
scanf("%d", &x);
if (vis[x]) {
update(x, -1);
vis[x]--;
}
else printf("No Elment!
");
}
else {
int a, k;
scanf("%d%d", &a, &k);
int l = 1, r = N;
int ans;
if (query(r) - query(a) < k)
printf("Not Find!
");
else {
int x = query(a) + k;
while (l <= r) {
int mid = (l + r) >> 1;
int res = query(mid);
if (res >= x) {
if (vis[mid] == 0) r = mid - 1;
else if (res - vis[mid] < x) {
ans = mid;
break;
}
else r = mid - 1;
}
else l = mid + 1;
}
printf("%d
", ans);
}
}
}
}
return 0;
}