HDUOJ-----2852 KiKi's K-Number（树状数组+二分）
HDUOJ-----2852 KiKi's K-Number（树状数组+二分）
KiKi's K-Number
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2393 Accepted Submission(s): 1101
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
这道题是一题，题意是要找a的第k大的数，由于想到树状数组，也有这么一种解法，所以就拿来练练手，首先采用传统的树状数组上升模式，进行
累加和，不过这里的和表示的是比a比大的个数，所以在我们查询的时候只要将要查找的的数sum(val)-sum(a)==k来进行二分，当然由于数据是离散的，而我们这里有无法进行离散化处理，因此我们只需要加入一个辅助数组lab[]，进行判断就可以了.....这道题，第一次遇到可算是想了一段时间，毕竟是个菜鸟....做出来还是很幸福的说....
代码如下：
1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 #define maxn 100000
5 #define lowbit(x) ((x)&(-x))
6 int aa[maxn+3];
7 int lab[maxn+3];
8 void ope(int x,int val)
9 {
10 while(x<=maxn)
11 {
12 aa[x]+=val;
13 x+=lowbit(x);
14 }
15 }
16 int cont(int x)
17 {
18 int ans=0;
19 while(x>0)
20 {
21 ans+=aa[x];
22 x-=lowbit(x);
23 }
24 return ans;
25 }
26 int main()
27 {
28 int n,p,a,k;
29 int left,right,mid,res;
30 bool tag=true;
31 // freopen("test.in","r",stdin);
32 //freopen("test.out","w",stdout);
33 while(scanf("%d",&n)!=EOF)
34 {
35 memset(aa,0,sizeof(aa));
36 memset(lab,0,sizeof(lab));
37 while(n--)
38 {
39 scanf("%d",&p);
40 if(p==2)
41 {
42 scanf("%d%d",&a,&k);
43 left=a, right=maxn;
44 tag=true;
45 while(left<=right)
46 {
47 mid=left+(right-left)/2;
48 res=cont(mid)-cont(a);
49 if(res<k)
50 left=mid+1;
51 else if(res-lab[mid]>=k)
52 right=mid-1;
53 else
54 if(res>=k&&res-lab[mid]<k)
55 {
56 printf("%d\n",mid);
57 tag=false;
58 break;
59 }
60 }
61 if(tag)
62 printf("Not Find!\n");
63
64 }
65 else
66 {
67 scanf("%d",&a);
68 if(p==1)
69 {
70 if(lab[a]==0)
71 printf("No Elment!\n");
72 else
73 {
74 lab[a]--;
75 ope(a,-1); //1代表insert
76 }
77 }
78 else
79 {
80 lab[a]++;
81 ope(a,1); //0代表elete
82 }
83 }
84 }
85 }
86 return 0;
87 }并给出一些数据来帮助验证吧....
1 5
2 0 5
3 1 2
4 0 6
5 2 3 2
6 2 8 1
7 7
8 0 2
9 0 2
10 0 4
11 2 1 1
12 2 1 2
13 2 1 3
14 2 1 4
15 12
16 0 2
17 0 2
18 0 4
19 0 5
20 1 2
21 0 6
22 2 3 2
23 2 8 1
24 2 1 1
25 2 1 2
26 2 1 3
27 2 1 4腾讯云开发者
