|
|
题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=2852
  /**//*
 题意：
给出三种操作，
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);
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;
}else
l = 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");
else
Add(e, -1);
}else {
scanf("%d %d", &a, &k);
int num = find(a, k);
if(num == maxn) {
printf("Not Find!\n");
}else
printf("%d\n", num);
}
}
}
return 0;
}
|