虽然这题在线段树的专题里面，，然而我并不觉得需要用线段树
维护一个set和stack,set里面的数字表示被摧毁的村庄节点，stack里面存放的是被摧毁的村庄节点
初始化，将0和n+1插入到set中，表示0和n+1村庄已被摧毁，，起到边界的作用
D t 将t插入到set中，将t压入栈中，表示t已经被摧毁
R 将栈的栈顶取出，并弹出，在set中删除对应的村庄编号
Q t 在set中找到<=t的元素记为L，在set中找到>=t的元素记为R，如果L或者R的某一个等于t，表示t已经存在于set中了，也就是t村庄已经被摧毁了，就输出0，否则输出R-L-1，因为L表示t左边最近被摧毁的村庄，R表示t右边最近被摧毁的村庄，那么R-L-1就表示中间连续没有被摧毁的数量，就是答案了
所以STL大法秒杀此题
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<string>
#include<iostream>
#include<functional>
#include<algorithm>using namespace std;
typedef long long LL;
typedef pair<LL, int> PLI;const int MX = 1e3 + 5;
const int INF = 0x3f3f3f3f;set<int>G;
stack<int>Last;int main() {int n, Q;while(~scanf("%d%d", &n, &Q)) {G.clear();while(!Last.empty()) Last.pop();G.insert(0);G.insert(n + 1);while(Q--) {char op[5]; int x;scanf("%s", op);if(op[0] == 'D') {scanf("%d", &x);G.insert(x);Last.push(x);} else if(op[0] == 'Q') {scanf("%d", &x);int L = *(--G.upper_bound(x));int R = *(G.lower_bound(x));if(L == x || R == x) {printf("0\n");} else {printf("%d\n", R - L - 1);}} else {int t = Last.top();Last.pop();G.erase(t);}}}return 0;
}