题目大意:
给定一个长为n的序列,两种询问,第一种询问长度至少为w的全0子序列的最靠左左位置是哪一位置,第二种是区间修改,即将一段区间全部改成0或全部改成1。
解题思路:
一般这种区间修改以及区间询问,包括这种询问满足某种特殊性质的区间是否存在的问题,我们都可以通过线段树这个数据结构来实现。线段数的功能不多,但是思想却十分优美,对于每道题都有其独特的解法。
许多人会认为线段树比较难,诚然,一开始就想到线段树的每个节点应该存什么信息是很难的,但是要沉下来,摸清套路之后一切就好办了。
对于询问满足某种特殊性质的区间是否存在的问题,我们一般要维护三个值,第一Tlen,维护这个节点所管辖的区间的满足某种特殊性质的区间的最长的值;第二Llen,维护这个区间从左开始的区间长度,第三Rlen,维护这个区间以右结尾的区间长度。那么为什么我们要维护后两个看似没有卵用的东西呢,难道第一个值维护好不就可以计算了吗?实际上,只维护第一个值Tlen是不行的,这样会存在各种问题,首先,你无法知道答案到底是在这个区间的左半边区间,还是在这个区间的右半边区间,还是横跨中点;其次,在每次区间修改之后,你无法以O(1)的时间复杂度去更新节点信息;最后,也是最根本的,如果没有后两个值,你根本求不出第一个值Tlen!!
当然,这种区间信息合并的线段树是比较难以实现的,有着诸多细节。我就说一些基本的套路,首先你需要更新Llen和Rlen这个最基本的值,Llen值显然等于这个区间的左半边区间的Llen值,若是整个左半边区间都是符合性质的区间,则Llen值可以扩宽至右半边区间。Rlen值同理与Llen。若是我们成功维护了Llen与Rlen,那么Tlen也就自然地可以维护了,即Tlen为左半边区间Tlen,右半边区间Tlen与横跨左右半边区间的Tlen中的最大值,而横跨左右半边区间的Tlen自然就是左Rlen+右Llen,这就是我们为什么要维护Llen和Rlen的原因。
代码:

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define MAXN 200005
#define L(a) ((a)<<1)
#define R(a) ((a)<<1|1)
using namespace std;
inline int read() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
int n, m;
struct Segment_Tree {
    int Le[MAXN], Re[MAXN];
    int Tlen[MAXN], Llen[MAXN], Rlen[MAXN];
    int Lazy[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; Lazy[p] = -1;
        Tlen[p] = 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);
    }
    
    void Update_len(int p) {
        if(Lazy[p] < 0) return;
        Tlen[p] = Llen[p] = Rlen[p] = (Lazy[p] ? 0 : len(p));
    }
    
    void Pushdown(int p) {
        if(Le[p]==Re[p] || Lazy[p]<0) return;
        Lazy[L(p)] = Lazy[R(p)] = Lazy[p];
        Lazy[p] = -1;
        Update_len(L(p)); Update_len(R(p));
    }
    
    void Update(int p) {
        Tlen[p] = max(max(Tlen[L(p)], Tlen[R(p)]), Rlen[L(p)]+Llen[R(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)];
    }
    
    int  Query(int p, int w) {
        if(Le[p] == Re[p]) { if(w==1) return Le[p]; else return 0; }
        Pushdown(p);
        if(Tlen[L(p)] >= w) return Query(L(p), w);
        else if(Rlen[L(p)]+Llen[R(p)] >= w) return (Re[L(p)]-Rlen[L(p)]+1);
        else if(Tlen[R(p)] >= w) return Query(R(p), w);
        else return 0;
    }
    
    void Modify(int p, int l, int r, int x) {
        if(Le[p]==l && Re[p]==r) {
            Lazy[p] = x; Update_len(p);
            return;
        }
        Pushdown(p);
        int mid = (Le[p] + Re[p]) >> 1;
        if(l > mid) Modify(R(p), l, r, x);
        else if(r <= mid) Modify(L(p), l, r, x);
        else { Modify(L(p), l, mid, x); Modify(R(p), mid+1, r, x); }
        Update(p);
    }
} T;

int main() {
    n=read(); m=read();
    T.Build(1, 1, n);
    while(m--) {
        int opt = read();
        if(opt == 1) {
            int w = read();
            int pos = T.Query(1, w);
            printf("%d\n", pos);
            if(pos > 0) T.Modify(1, pos, pos+w-1, 1);
        }
        else {
            int pos=read(), w=read();
            T.Modify(1, pos, pos+w-1, 0);
        }
    }
    return 0;
}