题意：
三个操作符
D x：摧毁第x个隧道
R x：修复上一个被摧毁的隧道，将摧毁的隧道入栈，修复就出栈
Q x：查询x所在的最长未摧毁隧道的区间长度。
1.如果当前区间全是未摧毁隧道，返回长度
2.如果在坐儿子的右区间或右儿子的左区间，返回这两个区间长度和
3.继续递归
#include <bits/stdc++.h> #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 using namespace std; const int MAXN = 55555; int mx[MAXN<<2], lmx[MAXN<<2], rmx[MAXN<<2]; int des[MAXN]; void push_up(int rt, int len) { lmx[rt] = lmx[rt<<1]; rmx[rt] = rmx[rt<<1|1]; if(lmx[rt] == len - (len >> 1)) lmx[rt] += lmx[rt<<1|1]; if(rmx[rt] == len >> 1) rmx[rt] += rmx[rt<<1]; mx[rt] = max(rmx[rt<<1] + lmx[rt<<1|1], max(mx[rt<<1], mx[rt<<1|1])); } void build(int l, int r, int rt) { mx[rt] = lmx[rt] = rmx[rt] = r - l + 1; if(l == r) return; int m = (l + r) >> 1; build(lson); build(rson); } void update(int p, int c, int l, int r, int rt) { if(l == r) { mx[rt] = c; lmx[rt] = c; rmx[rt] = c; return; } int m = (l + r) >> 1; if(p <= m) update(p, c, lson); else update(p, c, rson); push_up(rt, r-l+1); } int query(int p, int l, int r, int rt) { if(mx[rt] == 0) return 0; if(mx[rt] == r - l + 1) return r - l + 1; int m = (l + r) >> 1; if(p > m - rmx[rt<<1] && p <= m + lmx[rt<<1|1]) return rmx[rt<<1] + lmx[rt<<1|1]; if(p <= m) return query(p, lson); return query(p, rson); } int main() { // freopen("in.txt", "r", stdin); int n, m; while(~scanf("%d%d", &n, &m)) { build(1, n, 1); int cnt = 0; while(m--) { int x; char op[3]; scanf("%s", op); if(op[0] == 'D') { scanf("%d ", &x); des[cnt++] = x; update(x, 0, 1, n, 1); } else if(op[0] == 'R') { if(cnt == 0) continue; update(des[--cnt], 1, 1, n, 1); } else { scanf("%d", &x); printf("%d ", query(x, 1, n, 1)); } } } return 0; }