Tunnel Warfare(树状数组+二分)

题意：输入n,m。n代表数轴的长度，m代表操作数。

D x: 摧毁点x

Q x: 询问村庄x最左与最右没有被摧毁的点的距离

R ：恢复最后一个被摧毁的点

 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
");
74             else
75             {
76                 x = sum(x);
77                 pos1 = binary_find(x);
78                 pos2 = binary_find(x+1);
79                 printf("%d
",pos2-pos1-1);
80             }
81         }
82     }
83     return 0;
84 }

View Code

STL 做法

 1 #include <stdio.h>
 2 #include <set>
 3 #include <stack>
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     char ch;
 9     int n,m,x;
10     set<int>s;
11     stack<int>p;
12     scanf("%d%d",&n,&m);
13     s.insert(0);//增加最小边界，保证查找第一个位置时它的前一个位置存在
14     s.insert(n+1);//增加最大边界，保证查找最后一个位置时它的后一位置存在
15     while(m--)
16     {
17         getchar();
18         scanf("%c",&ch);
19         if (ch=='D')
20         {
21             scanf("%d",&x);
22             s.insert(x);//s中储存被摧毁的点，且自动将键值从小到大排列
23             p.push(x);//用栈保存被摧毁的点，方便最后一个被摧毁的点的恢复
24         }
25         else if (ch=='R')
26         {
27             x = p.top();//取出最后一个被摧毁的点
28             p.pop();//从栈中删除该点
29             s.erase(x);//从s中删除该点
30         }
31         else
32         {
33             scanf("%d",&x);
34             int r = *(s.lower_bound(x));//r表示值>=x的第一个值，即x右边的被摧毁的点中最接近x的点
35             int l = *(--s.lower_bound(x));//l表示x左边的被摧毁的点中最接近x的点
36             if (r==x)//如果查询的点在s中被找到，说明该点已被摧毁
37                 printf("0
");
38             else
39                 printf("%d
",r-l-1);//与x连续的没被摧毁的村庄个数
40         }
41     }
42     return 0;
43 }

View Code