[原创]HDU 2852 KiKi’s K-Number [树状数组+二分答案]【数据结构】

2016-11-09 20:47:06 Tabris_ 阅读数：262

博客爬取于2020-06-14 22:42:42
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/53105883

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2852

-----------------------------------------------------------.
KiKi’s K-Number

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3865 Accepted Submission(s): 1716

Problem Description
For the k-th number, we all should be very familiar with it. Of course,to kiki it is also simple. Now Kiki meets a very similar problem, kiki wants to design a container, the container is to support the three operations.

Push: Push a given element e to container

Pop: Pop element of a given e from container

Query: Given two elements a and k, query the kth larger number which greater than a in container;

Although Kiki is very intelligent, she can not think of how to do it, can you help her to solve this problem?

Input
Input some groups of test data ,each test data the first number is an integer m (1 <= m <100000), means that the number of operation to do. The next m lines, each line will be an integer p at the beginning, p which has three values:
If p is 0, then there will be an integer e (0 < e <100000), means press element e into Container.

If p is 1, then there will be an integer e (0 < e <100000), indicated that delete the element e from the container

If p is 2, then there will be two integers a and k (0 < a <100000, 0 < k <10000),means the inquiries, the element is greater than a, and the k-th larger number.

Output
For each deletion, if you want to delete the element which does not exist, the output “No Elment!”. For each query, output the suitable answers in line .if the number does not exist, the output “Not Find!”.

Sample Input
5
0 5
1 2
0 6
2 3 2
2 8 1
7
0 2
0 2
0 4
2 1 1
2 1 2
2 1 3
2 1 4

Sample Output
No Elment!
6
Not Find!
2
2
4
Not Find!

Source
2009 Multi-University Training Contest 4 - Host by HDU

-----------------------------------------------------------.

题目大意：
就是有N个操作 ，操作一共有3种
1） 0 的时候 就是在集合中加上一个e
2） 1 的时候 就是在集合中删除一个e
3） 2 的时候 就是找到在集合中比a大的第K个数

解题思路：
因为数一直是在1e6以内的 所以我们只要将其放在一个树状数组中就行了

这样的话对于 1，2操作就非常好处理了 ，利用桶的思想，记录一下就行了

但是对于3操作的话 就不行了，因为直接暴力的话会TLE啊 ，
所以我们只要二分一下答案 就可以了；

还是很简单啊 。

附本题代码

---------------------------------------------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
# include <bits/stdc++.h>

# define abs(x)          (((x)>0)?(x):-(x))
# define lalal           puts("*********")
# define Rep(a,b,c)      for(int a=(b);a<=(c);a++)
# define Req(a,b,c)      for(int a=(b);a>=(c);a--)
# define Rop(a,b,c)      for(int a=(b);a<(c);a++)
# define s1(a)           scanf("%d",&a)
typedef long long int LL;
using namespace std;
/**************************************/
const int N = 100000+5;
# define lowbit(x) (x&-x)
LL sum[N];
int h[N];
void update(int index,int val){
    for(int i=index;i<=N;i+=lowbit(i))
        sum[i]+=val;
    return ;
}

LL getSum(int index){
    LL ans=0;
    for(int i=index;i>0;i-=lowbit(i))
        ans+=sum[i];
    return ans;
}
LL cal(int l,int r){
    return getSum(r)-getSum(l);//因为是比a大 所以不用-1;
}
int main(){
    int n;
    while(~s1(n)){
        memset(sum,0,sizeof(sum));
        memset(h,0,sizeof(h));
        int op,e,a,k;
        while(n--){
            s1(op);
            if(0==op){
                s1(e);
                update(e,1);
                h[e]++;
            }
            else if(1==op){
                s1(e);
                if(h[e]>0) update(e,-1),h[e]--;
                else    puts("No Elment!");
            }
            else {
                s1(a),s1(k);
                int l=a,r=100000,mid,ret=-1;
                while(l<=r){
                    mid=(l+r)>>1;
                    if(cal(a,mid)>=k){
                        ret = mid;
                        r = mid-1;
                    }
                    else l = mid+1;
                }
                if(-1==ret) puts("Not Find!");
                else        printf("%d\n",ret);
            }
        }
    }
    return 0;
}