hdu 2852 KiKi's K-Number

点击打开hdu 2852

思路: 树状数组

分析:

1 题目给定三种操作: 0 x 表示把x插入容器 ; 1 x 表示删除一个x如果没有x则输出 No Elment! ; 2 a k 表示比a大的数中的第k大的数 如果没有输出No Find!

2 我们先来看一下树状数组的功能，树状数组能够在在logN的时间内求出某段区间的和，那么对于2 a k这种操作我们可以看成是求是否有x满足[a,x]这个区间的和为k，那么这样就变成了树状数组的求和问题了。那我们再来考虑插入和删除操作，插入一个x相当于更新树状数组，删除x注意多个的情况

3 通过第2点的分析我们知道我们主要是否有区间[a , x]的和为k，那么我们知道对于树状数组来说从a开始的区间的和是递增的，因此我们可以通过二分答案，然后去求出满足的x

4 那么我们来分析一下时间复杂度，枚举操作为O(n)，每次操作的最坏时间为O(logN)，因此时间复杂度为O(n*logN);

代码;

/***********************************************
* By: chenguolin                               * 
* Date: 2013-08-20                             *
* Address: http://blog.csdn.net/chenguolinblog *
***********************************************/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 100010;

int n;
bool vis[MAXN];
int treeNum[MAXN];

int lowbit(int x){
    return x&(-x);
}

int getSum(int x){
    int sum = 0;
    while(x){
         sum += treeNum[x];
         x -= lowbit(x);
    }
    return sum;
}

void add(int x , int val){
    while(x < MAXN){
         treeNum[x] += val;
         x += lowbit(x);
    }
}

int search(int l , int x){
    int left = l+1;
    int right = MAXN-1;
    while(left <= right){
        int mid = (left+right)>>1;
        int sum = getSum(mid)-getSum(l);
        if(sum == x){
            if(vis[mid])
               return mid;
            right = mid-1;
        }
        else if(sum < x)
            left = mid+1;
        else{
            if(getSum(mid-1)-getSum(l) < x)
                return mid;
            right = mid-1;
        }
    }
    return -1;
}

void solve(){
    int mark , x , y;
    memset(vis , false , sizeof(vis));
    memset(treeNum , 0 , sizeof(treeNum));
    for(int i = 0 ; i < n ; i++){
        scanf("%d" , &mark); 
        if(mark == 0){
            scanf("%d" , &x);
            add(x , 1);
            vis[x] = true;
        }
        else if(mark == 1){
            scanf("%d" , &x);
            int sum = getSum(x)-getSum(x-1);
            if(sum == 0)
                puts("No Elment!");
            else{
                add(x , -1);
                if(sum == 1)
                   vis[x] = false;
            }
        }
        else{
            scanf("%d%d" , &x , &y);
            int ans = search(x , y);
            if(ans == -1)
                puts("Not Find!");
            else
                printf("%d\n" , ans);
        }
    }
}

int main(){
    while(scanf("%d" , &n) != EOF)
         solve();         
    return 0;
}