|
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=2852
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) /**//*
题意:
给出三种操作,
0 在容器中插入一个数。
1 在容器中删除一个数。
2 求出容器中大于a的第k大元素。
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
解法:
二分+树状数组
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
思路:
树状数组的特点就是对点更新,成段求和,而且常数非常小。原始
的树状数组只有两种操作,在某点插入一个数 和 求1到i的所有数的和。
这道题目一共有三种操作,但是实质上其实只有两种:插入和询问。插入
操作和删除操作可以视为一种,只不过一个是将标记+1,另一个是-1,而
插入的数对应于树状数组的下标,这样就可以在log(n)的时间内完成插入
和删除。求大于a的k大元素,可以通过二分枚举答案来完成,枚举的是当
前答案在树状数组中的位置,设为m,然后对v[a+1] v[m]求和就是小
于等于m的数的个数,这一步可以用树状数组的求和操作来完成,然后根据
和k的比较来调整m的位置。询问的复杂度也是log(n)的。
*/
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#include <iostream>
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
using namespace std;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
#define maxn 100002
int C[maxn], n;
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int lowbit(int x) {
return x & (-x);
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) void Add(int pos, int val) {
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(pos < maxn) {
C[pos] += val;
pos += lowbit(pos);
}
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int Sum(int pos) {
int S = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(pos >= 1) {
S += C[pos];
pos -= lowbit(pos);
}
return S;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int find(int a, int k) {
int l = a + 1;
int r = maxn - 1;
int S = Sum(a);
int ans = maxn;
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(l <= r) {
int m = (l + r) >> 1;
int nS = Sum(m);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(nS - S >= k) {
r = m - 1;
if(m < ans)
ans = m;
}else
l = m + 1;
}
![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
return ans;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) int main() {
int n;
int i;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(scanf("%d", &n) != EOF) {
for(i = 1; i < maxn; i++)
C[i] = 0;
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) while(n--) {
int id, e, a, k;
scanf("%d", &id);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(id == 0) {
scanf("%d", &e);
Add(e, 1);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }else if(id == 1) {
scanf("%d", &e);
if(Sum(e) - Sum(e-1) == 0)
printf("No Elment!\n");
else
Add(e, -1);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) }else {
scanf("%d %d", &a, &k);
int num = find(a, k);
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) if(num == maxn) {
printf("Not Find!\n");
}else
printf("%d\n", num);
}
}
}
return 0;
}
|