|
|
題目鏈接： http://acm.hdu.edu.cn/showproblem.php?pid=2852
  /**//*
 題意：
給出三種操作，
0 在容器中插入一個數(shù)。
1 在容器中刪除一個數(shù)。
2 求出容器中大于a的第k大元素。
解法：
二分+樹狀數(shù)組
思路：
樹狀數(shù)組的特點就是對點更新，成段求和，而且常數(shù)非常小。原始
的樹狀數(shù)組只有兩種操作，在某點插入一個數(shù) 和 求1到i的所有數(shù)的和。
這道題目一共有三種操作，但是實質(zhì)上其實只有兩種：插入和詢問。插入
操作和刪除操作可以視為一種，只不過一個是將標(biāo)記+1，另一個是-1，而
插入的數(shù)對應(yīng)于樹狀數(shù)組的下標(biāo)，這樣就可以在log(n)的時間內(nèi)完成插入
和刪除。求大于a的k大元素，可以通過二分枚舉答案來完成，枚舉的是當(dāng)
前答案在樹狀數(shù)組中的位置，設(shè)為m，然后對v[a+1]  v[m]求和就是小
于等于m的數(shù)的個數(shù)，這一步可以用樹狀數(shù)組的求和操作來完成，然后根據(jù)
和k的比較來調(diào)整m的位置。詢問的復(fù)雜度也是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;
}
|