poj 2892 stl或线段树

标准解法应该是线段树，这里提供另一种思路：将“断点”（即被摧毁的村庄）放入stl的容器（我用的是set）中维护，对于每次查询，只要找这个数在哪两个断点之间即可，写起来轻松愉快。

PS：hdu上的数据略坑，同一个村庄可以被摧毁多次，恢复的时候一次恢复就可以让它不再是断点，但是第一次恢复以后剩下几次也是需要恢复的...所以不能把它被摧毁的记录删除，另外没有被摧毁的村庄时也有R操作。poj上的数据比较规范，符合实际情况，没有上面的奇怪数据。

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <stack>
 6 #include <set>
 7 using namespace std;
 8 
 9 set<int> s;
10 set<int>::iterator it;
11 stack<int> st;
12 
13 int main ()
14 {
15     int n, m;
16     while ( scanf("%d%d", &n, &m) != EOF )
17     {
18         while ( !st.empty() ) st.pop();
19         s.clear();
20         char op[2];
21         int x;
22         while ( m-- )
23         {
24             scanf("%s", op);
25             if ( op[0] == 'D' )
26             {
27                 scanf("%d", &x);
28                 s.insert(x);
29                 st.push(x);
30             }
31             else if ( op[0] == 'Q' )
32             {
33                 scanf("%d", &x);
34                 if ( s.find(x) != s.end() )
35                 {
36                     printf("0
");
37                 }
38                 else
39                 {
40                     int l = 1, r = n;
41                     it = s.upper_bound(x);
42                     if ( it != s.end() )
43                     {
44                         r = (*it) - 1;
45                     }
46                     if ( it != s.begin() )
47                     {
48                         it--;
49                         l = (*it) + 1;
50                     }
51                     printf("%d
", r - l + 1);
52                 }
53             }
54             else
55             {
56                 if ( st.empty() ) continue;
57                 int tmp = st.top();
58                 st.pop();
59                 s.erase(tmp);
60             }
61         }
62     }
63     return 0;
64 }