本文主要是介绍HDU 2852 KiKi's K-Number *（树状数组），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给出三种操作，
0在容器中插入一个数。
1在容器中删除一个数。
2求出容器中大于a的第k大元素。
二分+树状数组
思路： 树状数组的特点就是对点更新，成段求和，而且常数非常小。原始的树状数组只有两种操作，在某点插入一个数 和 求1到i的所有数的和。这道题目一共有三种操作，但是实质上其实只有两种：插入和询问。插入操作和删除操作可以视为一种，只不过一个是将标记+1，另一个是-1，而插入的数对应于树状数组的下标，这样就可以在log(n)的时间内完成插入和删除。求大于a的k大元素，可以通过二分枚举答案来完成，枚举的是当前答案在树状数组中的位置，设为m，然后对v[a+1] v[m]求和就是小于等于m的数的个数，这一步可以用树状数组的求和操作来完成，然后根据和k的比较来调整m的位置。询问的复杂度也是log(n)的。
代码：
#include <iostream>
using namespace std;
#define maxn 100002
int C[maxn], n;
int lowbit(int x) { return x & (-x);
}
void Add(int pos, int val) {while(pos < maxn) {C[pos] += val;pos += lowbit(pos);}
}
int Sum(int pos) {int S = 0;while(pos >= 1) {S += C[pos];pos -= lowbit(pos);}return S;
}int find(int a, int k) {int l = a + 1;int r = maxn - 1;int S = Sum(a); //代表的是比a小的数的个数int ans = maxn;while(l <= r) {int m = (l + r) >> 1;int nS = Sum(m);if(nS - S >= k) {r = m - 1;if(m < ans)ans = m;}elsel = m + 1;}return ans;
}int main() {int n;int i;while(scanf("%d", &n) != EOF) {for(i = 1; i < maxn; i++)C[i] = 0;while(n--) {int id, e, a, k;scanf("%d", &id);if(id == 0) {scanf("%d", &e);Add(e, 1);}else if(id == 1) {scanf("%d", &e);if(Sum(e) - Sum(e-1) == 0)printf("No Elment!\n");elseAdd(e, -1);}else {scanf("%d %d", &a, &k);int num = find(a, k);if(num == maxn) {printf("Not Find!\n");}elseprintf("%d\n", num);}}}return 0;
}
这篇关于HDU 2852 KiKi's K-Number *（树状数组）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
