随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

HDU 2852 KiKi's K-Number

题目链接: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;
}

posted on 2011-03-31 13:10 英雄哪里出来 阅读(1438) 评论(0)  编辑 收藏 引用 所属分类: 树状数组


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理