线段树求一个点所处区间的最大连续长度，用lsum记录区间的左连续长度，rsum记录区间的
右连续长度，查询时判断p点处于左子树还是右子树，然后计算左子树的右连续长度+右子树
的左连续长度的和。
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<algorithm> using namespace std; #define lson l, mid, rt << 1 #define rson mid + 1, r, rt << 1 | 1const int MAXN = 50050; int lsum[MAXN << 2], rsum[MAXN << 2]; int stack[MAXN]; int n, m;void build(int l, int r, int rt) {int mid = l + r >> 1;lsum[rt] = rsum[rt] = r - l + 1;if(l == r) return;build(lson);build(rson); }void PushUp(int l, int r, int rt) {int mid = l + r >> 1;lsum[rt] = lsum[rt << 1];rsum[rt] = rsum[rt << 1 | 1];if(lsum[rt << 1] == mid - l + 1)lsum[rt] += lsum[rt << 1 | 1];if(rsum[rt << 1 | 1] == r - mid)rsum[rt] += rsum[rt << 1]; }void update(int c, int p, int l, int r, int rt) {int mid = l + r >> 1;if(p <= l && r <= p){lsum[rt] = rsum[rt] = c;return;}if(p <= mid)update(c, p, lson);elseupdate(c, p, rson);PushUp(l, r, rt); }int query(int p, int l, int r, int rt) {int mid = l + r >> 1;if(p <= l && r <= p){return lsum[rt];}if(p <= mid){if(mid - rsum[rt << 1] + 1 <= p) //判断p所处的位置 {return rsum[rt << 1] + lsum[rt << 1 | 1];}elsereturn query(p, lson);}else{if(mid + 1 + lsum[rt << 1 | 1] - 1 >= p){return rsum[rt << 1] + lsum[rt << 1 | 1];}elsereturn query(p, rson);} }void operation() {int top = 0, x;char op[5];while(m --){scanf("%s", op);if('D' == op[0]){scanf("%d", &x);stack[++ top] = x;update(0, x, 1, n, 1);}else if('Q' == op[0]){scanf("%d", &x);printf("%d\n", query(x, 1, n, 1));}else{x = stack[top --];update(1, x, 1, n, 1);}} }int main() {while(scanf("%d%d", &n, &m) == 2){build(1, n, 1);operation();}return 0; }
