hdu 2852 KiKis K-Number

思路: 樹狀數組

分析:

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;
}