POJ 2892 Tunnel Warfare(树状数组+二分)

二分求上界和下界，树状数组。注意特殊情况。
  1 #include <cstring>
  2 #include <cstdio>
  3 #include <string>
  4 #include <iostream>
  5 #include <algorithm>
  6 #include <vector>
  7 using namespace std;
  8 int p[100001];
  9 int o[100001];
 10 int stack[100001];
 11 int n;
 12 int lowbit(int t)
 13 {
 14     return t&(-t);
 15 }
 16 void insert(int t,int d)
 17 {
 18     while(t <= n)
 19     {
 20         p[t] += d;
 21         t += lowbit(t);
 22     }
 23 }
 24 int getsum(int t)
 25 {
 26     int sum = 0;
 27     while(t > 0)
 28     {
 29         sum += p[t];
 30         t -= lowbit(t);
 31     }
 32     return sum;
 33 }
 34 int fr(int x)
 35 {
 36     int str,end,temp,mid;
 37     str = 1;
 38     end = n;
 39     while(str < end)
 40     {
 41         mid = (str+end+1)/2;
 42         temp = getsum(mid);
 43         if(temp > x)
 44             end = mid-1;
 45         else
 46             str = mid;
 47     }
 48     return end;
 49 }
 50 int fl(int x)
 51 {
 52     int str,end,temp,mid;
 53     str = 1;
 54     end = n;
 55     while(str < end)
 56     {
 57         mid = (str+end)/2;
 58         temp = getsum(mid);
 59         if(temp < x)
 60             str = mid+1;
 61         else
 62             end = mid;
 63     }
 64     return str;
 65 }
 66 int main()
 67 {
 68     int i,m,top,num,t;
 69     char ch[12];
 70     while(scanf("%d%d",&n,&m)!=EOF)
 71     {
 72         top = 0;
 73         for(i = 1;i <= n;i ++)
 74         {
 75             p[i] = 0;
 76             o[i] = 0;
 77         }
 78         for(i = 1; i <= m; i ++)
 79         {
 80             scanf("%s",ch);
 81             if(ch[0] == 'R')
 82             {
 83                 if(top != 0)
 84                 {
 85                     o[stack[top]] = 0;
 86                     insert(stack[top--],-1);
 87                 }
 88             }
 89             else if(ch[0] == 'D')
 90             {
 91                 scanf("%d",&num);
 92                 stack[++top] = num;
 93                 if(o[num] == 0)
 94                 {
 95                     o[num] = 1;
 96                     insert(num,1);
 97                 }
 98             }
 99             else if(ch[0] == 'Q')
100             {
101                 scanf("%d",&num);
102                 if(o[num])
103                     printf("0
");
104                 else
105                 {
106                     t = getsum(num);
107                     if(t == 0)//注意一下
108                     printf("%d
",fr(t));
109                     else
110                     printf("%d
",fr(t)-fl(t));
111                 }
112             }
113         }
114     }
115     return 0;
116 }