HDU 2852 KiKi's K-Number(离线+树状数组)

省赛训练赛上一题，貌似不难啊。当初，没做出。离线+树状数组+二分。
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 using namespace std;
 5 #define N 100000
 6 int p[100100];
 7 int qur[300001][3];
 8 int lowbit(int t)
 9 {
10     return t&(-t);
11 }
12 void insert(int t,int d)
13 {
14     while(t <= N)
15     {
16         p[t] += d;
17         t += lowbit(t);
18     }
19 }
20 int getsum(int t)
21 {
22     int sum = 0;
23     while(t)
24     {
25         sum += p[t];
26         t -= lowbit(t);
27     }
28     return sum;
29 }
30 int bin(int x)
31 {
32     int str,end,mid;
33     if(x > getsum(N))
34     return -1;
35     str = 1;
36     end = N;
37     while(str < end)
38     {
39         mid = (str + end)/2;
40         if(getsum(mid) < x)
41         str = mid + 1;
42         else
43         end = mid;
44     }
45     return str;
46 }
47 int main()
48 {
49     int n,i;
50     while(scanf("%d",&n)!=EOF)
51     {
52         memset(p,0,sizeof(p));
53         for(i = 0;i < n;i ++)
54         {
55            scanf("%d",&qur[i][0]);
56            if(qur[i][0] == 0||qur[i][0] == 1)
57            scanf("%d",&qur[i][1]);
58            else
59            scanf("%d%d",&qur[i][1],&qur[i][2]);
60         }
61         for(i = 0;i < n;i ++)
62         {
63             if(qur[i][0] == 0)
64             insert(qur[i][1],1);
65             else if(qur[i][0] == 1)
66             {
67                 if(getsum(qur[i][1])-getsum(qur[i][1]-1) > 0)
68                 insert(qur[i][1],-1);
69                 else
70                 printf("No Elment!
");
71             }
72             else
73             {
74                 int flag;
75                 flag = bin(getsum(qur[i][1])+qur[i][2]);
76                 if(flag == -1)
77                 printf("Not Find!
");
78                 else
79                 printf("%d
",flag);
80             }
81         }
82     }
83     return 0;
84 }