洛谷 P1503 鬼子进村
Description
描述 县城里有n个用地道相连的房子，第i个只与第i-1和第i+1个相连。这是有m个消息依次传来
1、消息为D x：鬼子将x号房子摧毁了，地道被堵上。
2、消息为R ：村民们将鬼子上一个摧毁的房子修复了。
3、消息为Q x：有一名士兵被围堵在x号房子中。
李云龙收到信息很紧张，他想知道每一个被围堵的士兵能够到达的房子有几个。
Input
第一行2个整数n，m（n，m<=50000）。
接下来m行，有如题目所说的三种信息共m条。
Output
- 对于每一个被围堵的士兵，输出该士兵能够到达的房子数。
Sample Input
7 9D 3D 6D 5Q 4Q 5RQ 4RQ 4
Sample Output
1
0
2
4
题解：
- 平衡树。
- 终于脱离了模版题的范畴。这题如果想到用平衡树思路就很容易想到了。用Treap维护被摧毁的房子位置，D操作就插入位置，Q操作（设给的当前位置为x）的答案就是(x的后继 - x的前继 - 1)。R操作弄一个栈依题意模拟即可。
- 还是一句话，平衡树的前继后继函数要巧用！
#include#include #include #include #define N 50005using namespace std;struct T {int l, r, val, dat;} t[N];int n, m, root, tot;stack stk;int read(){ int x = 0; char c = getchar(); while(c < '0' || c > '9') c = getchar(); while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();} return x;}int New(int val){ t[++tot].val = val; t[tot].dat = rand(); return tot;}void zig(int &y){ int x = t[y].l; t[y].l = t[x].r, t[x].r = y, y = x;}void zag(int &x){ int y = t[x].r; t[x].r = t[y].l, t[y].l = x, x = y;}void insert(int &p, int val){ if(!p) {p = New(val); return;} if(val == t[p].val) return; if(val < t[p].val) { insert(t[p].l, val); if(t[t[p].l].dat > t[p].dat) zig(p); } else { insert(t[p].r, val); if(t[t[p].r].dat > t[p].dat) zag(p); }}void erase(int &p, int val){ if(!p) return; if(val == t[p].val) { if(t[p].l || t[p].r) { if(!t[p].r || t[t[p].l].dat > t[p].dat) zig(p), erase(t[p].r, val); else zag(p), erase(t[p].l, val); } else p = 0; return; } val < t[p].val ? erase(t[p].l, val) : erase(t[p].r, val);}int preNext(int op, int val){ int ans = op == 0 ? 2 : 1, p = root; while(p) { if(val == t[p].val) { if(!op && t[p].l) { p = t[p].l; while(t[p].r) p = t[p].r; ans = p; break; } else if(!op) break; if(op && t[p].r) { p = t[p].r; while(t[p].l) p = t[p].l; ans = p; break; } else if(op) break; } if(!op && t[p].val < val && t[p].val > t[ans].val) ans = p; if(op && t[p].val > val && t[p].val < t[ans].val) ans = p; p = val < t[p].val ? t[p].l : t[p].r; } return t[ans].val;}bool find(int p, int val){ if(!p) return 0; if(val == t[p].val) return 1; if(val < t[p].val) return find(t[p].l, val); else return find(t[p].r, val);}int main(){ cin >> n >> m; New(n + 1), New(0), root = 1, t[1].l = 2; for(int i = 1; i <= m; i++) { char c[2]; scanf("%s", c); if(c[0] == 'D') { int x = read(); insert(root, x); stk.push(x); } else if(c[0] == 'R') { erase(root, stk.top()); stk.pop(); } else if(c[0] == 'Q') { int x = read(); if(find(root, x)) printf("0\n"); else printf("%d\n", preNext(1, x) - preNext(0, x) - 1); } } return 0;}