题意：
给你n 个数（1，2，3，，，n），刚开始都是连续的， 有三种操作：
1. 将某个数x 切割开（变的不连续）
2. 恢复上一个切割的数（变的连续）
3. 查询x 位置数， 最长连续的长度。
思路：
线段树：
需要维护 l 表示这个区间从左端点开始最大连续长度
r 表示这个区间从右端点开始的最大连续长度
m 表示这个区间的最大连续长度。
整体是单点更新，单点查询。 就是pushup比较麻烦点。
先更新父区间的l，r 在根据儿子区间 来更新m。
查询稍微有些类似主席树的查询
有几个坑：
修复时，可能会修复一个 未切割的结点（这时候应该不操作！！！）
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <cmath> #include <stack> using namespace std; int T; /** 整体是单点更新，单点查询。 就是向上合并比较麻烦，想清楚还是很简单的。 **/ const int maxn = 50000 + 10; int n, m; char cmd[3]; stack<int>sk; int bad[maxn]; struct Node{ int v; /// v 是值，要么是1，要么是0 int l,r,m; /// l表示这个区间的右端点最大连续长度，r表示区间左端点最大连续长度，m是最大连续长度。 int L,R; /// 区间[L,R]; }nod[maxn<<2]; void pushup(int o){ int lson = o<<1; int rson = o<<1|1; nod[o].l = nod[lson].l; nod[o].r = nod[rson].r; if (nod[lson].l == nod[lson].R - nod[lson].L + 1){ nod[o].l += nod[rson].l; } if (nod[rson].r == nod[rson].R - nod[rson].L + 1){ nod[o].r += nod[lson].r; } nod[o].m = max(nod[o].l, max(nod[o].r, max(nod[lson].m, nod[rson].m))); } void build(int l,int r,int o){ nod[o].L = l; nod[o].R = r; if (l == r){ nod[o].v = nod[o].l = nod[o].r = nod[o].m = 1; return; } int m = l + r >> 1; build(l, m, o << 1); build(m+1, r, o << 1 | 1); pushup(o); } void update(int pos, int c, int l,int r,int o){ if (l == r){ nod[o].v = c; if (nod[o].v == 0){ nod[o].l = nod[o].r = nod[o].m = 0; } else { nod[o].l = nod[o].r = nod[o].m = 1; } return; } int m = l + r >> 1; if (m >= pos){ update(pos, c, l, m, o << 1); } else update(pos, c, m+1, r, o << 1 | 1); pushup(o); } int query(int pos,int l,int r,int o){ if (l == r){ return nod[o].m; } if (nod[o].m == nod[o].R - nod[o].L + 1) return nod[o].m; /// 小小的剪枝 int m = l + r >> 1; int lson = o<<1; int rson = o << 1|1; if (m >= pos){ if (nod[lson].r >= nod[lson].R - pos + 1){ return nod[rson].l + query(pos, l, m, lson); } else { return query(pos, l, m, lson); } } else { if (nod[rson].l >= pos - nod[rson].L + 1){ return nod[lson].r + query(pos, m+1, r, rson); } else { return query(pos, m+1,r,rson); } } } int main(){ while(~scanf("%d %d", &n, &m)){ build(1,n,1); memset(bad,0,sizeof bad); while(!sk.empty()) sk.pop(); while(m--){ scanf("%s", cmd); if (cmd[0] == 'R'){ if (!sk.empty()){ int x = sk.top(); sk.pop(); if (bad[x] == 0) continue; /// 注意,可能修复一个好的结点！！！ bad[x] = 0; update(x, 1, 1, n, 1); } } else if (cmd[0] == 'D'){ int x; scanf("%d",&x); bad[x] = 1; sk.push(x); update(x, 0, 1, n, 1); } else { int x; scanf("%d",&x); printf("%d\n", query(x,1,n,1)); } } } return 0; }