Tunnel Warfare(树状数组+二分)

 1 #include <stdio.h>
 2 #include <string.h>
 3 const int N=50001;
 4 int c[N],keep[N],n;
 5 bool vis[N];
 6 
 7 int lowbit(int x)
 8 {
 9     return x&(-x);
10 }
11 int sum(int x)
12 {
13     int res = 0;
14     while(x > 0)
15     {
16         res+=c[x];
17         x-=lowbit(x);
18     }
19     return res;
20 }
21 void add(int x,int d)
22 {
23     while(x <= n)
24     {
25         c[x]+=d;
26         x+=lowbit(x);
27     }
28 }
29 int binary_find(int key)
30 {
31     int l = 1,r = n+1,pos = n+2;
32     while(l <= r)
33     {
34         int mid = (l+r)>>1;
35         if (sum(mid) >= key)
36         {
37             r = mid-1;
38             pos = mid;
39         }
40         else
41             l = mid+1;
42     }
43     return pos;
44 }
45 int main()
46 {
47     char ch;
48     int m,x,t = 0;
49     scanf("%d%d",&n,&m);
50     for (int i = 0; i < m; i++)
51     {
52         getchar();
53         scanf("%c",&ch);
54         if (ch==‘D‘)
55         {
56             scanf("%d",&x);
57             keep[++t] = ++x;
58             vis[x] = true;
59             add(x,1);
60         }
61         else if (ch==‘R‘)
62         {
63             x = keep[t--];
64             vis[x] = false;
65             add(x,-1);
66         }
67         else
68         {
69             int pos1,pos2;
70             scanf("%d",&x);
71             x++;
72             if (vis[x])
73                 printf("0\n");
74             else
75             {
76                 x = sum(x);
77                 pos1 = binary_find(x);
78                 pos2 = binary_find(x+1);
79                 printf("%d\n",pos2-pos1-1);
80             }
81         }
82     }
83     return 0;
84 }