题目大意:
给定一个长为n的01序列,我们用0表示不可走,1表示可走,实现三种操作:第一种:$(Q, x)$询问从某个点开始,向其左右最多可以扩展多宽,即询问包含这一位置的最长的全1序列是多长;第二种:$(D, x)$将某一个点的状态改成0;第三种:$(R)$将最近一次被修改成0的点还原成1。
解题思路:
这道题想到正解不难,即每个点维护其管辖的区间的开头有多长的全1序列,结尾有多长的全1序列即可。但是细节多到爆炸而且题面里都没有讲清楚这些细节,搞得我跳了半个小时。首先,这题是多组数据(妈的题面里也不讲样例给的也是一组);其次,数据中的R操作可能非法,即没有被改成0的点;再者,一个点可以被多次改成0,并且需要更新这个点为最后一次修改的点。2333,我理解力太差了。
一些其他细节见代码,代码很好写也不要lazy标记。
代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <stack>
#include <algorithm>
#define MAXN 400005
#define L(a) ((a)<<1)
#define R(a) ((a)<<1|1)
using namespace std;
int n, m, x;
bool ex[MAXN];
stack<int> Destroyed_Village;
struct Segment_Tree {
    int Le[MAXN], Re[MAXN];
    int Llen[MAXN], Rlen[MAXN];
    inline int len(int p) { return Re[p]-Le[p]+1; }
    
    void Build(int p, int l, int r) {
        Le[p] = l; Re[p] = r;
        Llen[p] = Rlen[p] = len(p);
        if(l == r) return;
        int mid = (l + r) >> 1;
        Build(L(p),l,mid); Build(R(p),mid+1,r);
    }
    
    int  Query_Rlen(int p, int l, int r) {
        if(Le[p]==l && Re[p]==r) return Rlen[p];
        int mid = (Le[p] + Re[p]) >> 1;
        if(r <= mid) return Query_Rlen(L(p), l, r);
        else if(l > mid) return Query_Rlen(R(p), l, r);
        else {
            if(Llen[R(p)] >= (r-mid)) return ((r-mid) + Query_Rlen(L(p), l, mid));
            else return Query_Rlen(R(p), mid+1, r);
        }
    }
    
    int  Query_Llen(int p, int l, int r) {
        if(Le[p]==l && Re[p]==r) return Llen[p];
        int mid = (Le[p] + Re[p]) >> 1;
        if(r <= mid) return Query_Llen(L(p), l, r);
        else if(l > mid) return Query_Llen(R(p), l, r);
        else {
            if(Rlen[L(p)] >= (mid-l+1)) return ((mid-l+1) + Query_Llen(R(p), mid+1, r));
            else return Query_Llen(L(p), l, mid);
        }
    }
    
    void Update(int p) {
        Llen[p] = Llen[L(p)];
        if(Llen[L(p)] == len(L(p))) Llen[p] += Llen[R(p)];
        Rlen[p] = Rlen[R(p)];
        if(Rlen[R(p)] == len(R(p))) Rlen[p] += Rlen[L(p)];
    }
    
    void Modify(int p, int x, int val) {
        if(Le[p] == Re[p]) { Llen[p] = Rlen[p] = val; return; }
        int mid = (Le[p] + Re[p]) >> 1;
        if(x <= mid) Modify(L(p), x, val);
        else Modify(R(p), x, val);
        Update(p);
    }
    
} T;

int main() {
    while(scanf("%d%d", &n, &m) != EOF) {
        T.Build(1, 1, n);
        memset(ex, true, sizeof(ex));
        while(m--) {
            char opt[2]; scanf("%s", opt);
            if(opt[0] == 'D') {
                scanf("%d", &x);
                if(ex[x]) {
                    ex[x] = false;
                    T.Modify(1, x, 0);
                }
                Destroyed_Village.push(x);
            }
            else if(opt[0] == 'Q') {
                scanf("%d", &x);
                printf("%d\n", max(0, T.Query_Rlen(1,1,x) + T.Query_Llen(1,x,n) - 1));
            }
            else {
                if(! Destroyed_Village.empty()) {
                    x = Destroyed_Village.top();
                    Destroyed_Village.pop();
                    if(ex[x]) continue;
                    ex[x] = true;
                    T.Modify(1, x, 1);
                }
            }
        }
    }
    
    return 0;
}