261 旅馆
线段树,类似于维护区间最大连续和,维护区间最长的连续0段长度,需要维护区间靠左得最长0段长度与区间靠右得最长0段长度,每次询问最靠左得长度为len的连续0段的l,所以query函数要重写........感受到了线段树的灵活性
#include <bits/stdc++.h>
using namespace std;
const int N=5e4+10;
using namespace std;
struct node //设计线段树节点
{
    int l, r;
    int add;
    int ld;
    int rd;
    int d;

}t[N * 4];
void push_up(node& rt, const node& ls, const node& rs)//定义上传操作，如求和
{
    rt.ld = ls.ld;
    if (ls.ld == ls.r - ls.l + 1)
    {
        rt.ld += rs.ld;
    }
    rt.rd = rs.rd;
    if (rs.ld == rs.r - rs.l + 1)
    {
        rt.rd += ls.rd;
    }
    rt.d = max(ls.rd + rs.ld, max(ls.d, rs.d));
}
void push_down(int k)
{
    if (t[k].add != 0)
    {
        if (t[k].add == 1)
        {
            t[k << 1].ld = t[k << 1].rd = t[k << 1].d = 0;
            t[k << 1].add = 1;
            t[k << 1 | 1].ld = t[k << 1 | 1].rd = t[k << 1 | 1].d = 0;
            t[k << 1 | 1].add = 1;
            t[k].add = 0;
        }
        else
        {
            t[k << 1].ld = t[k << 1].rd = t[k << 1].d = t[k << 1].r - t[k << 1].l + 1;
            t[k << 1].add = -1;
            t[k << 1 | 1].ld = t[k << 1 | 1].rd = t[k << 1 | 1].d =t[k << 1|1].r - t[k << 1|1].l + 1;
            t[k << 1 | 1].add = -1;
            t[k].add = 0;
        }
    }
}
void mark(node& rt, long long val)//定义标记操作
{
    if (val == 1)
    {
        rt.ld = rt.rd = rt.d = 0;
        rt.add = 1;
    }
    else
    {
        rt.ld = rt.rd = rt.d = rt.r-rt.l+1;
        rt.add = -1;
    }
}

void build(int k, int l, int r)
{
    if (l == r)//定义叶节点初始化操作
    {
        t[k] = { l, r, 0,1,1,1 };
        return;
    }
    int mid = (l + r) / 2;
    build(k << 1, l, mid);
    build(k << 1 | 1, mid + 1, r);
    push_up(t[k], t[k << 1], t[k << 1 | 1]);
    t[k].l = l, t[k].r = r, t[k].add = 0;
}
void modify(int k, int x, int y, long long val)  //修改操作
{
    if (x > y) return;
    if (x <= t[k].l && t[k].r <= y) return mark(t[k], val);
    push_down(k);
    int mid = (t[k].l + t[k].r) / 2;
    if (x <= mid) modify(k << 1, x, y, val);
    if (y > mid) modify(k << 1 | 1, x, y, val);
    push_up(t[k], t[k << 1], t[k << 1 | 1]);
}
int query(int k, int len)
{
    if (t[k].d < len)
    {
        return 0;
    }
    push_down(k);
    if (t[k << 1].d >= len)
    {
        return query(k << 1, len);
    }
    if (t[k << 1].rd + t[k << 1 | 1].ld >= len)
    {
        return t[k << 1].r - t[k << 1].rd+1;
    }
    if (t[k << 1 | 1].d >= len)
    {
        return query(k << 1 | 1, len);
    }
    return 0;
}
int main()
{
    int n, m;
    cin >> n >> m;
    build(1, 1, n);
    while (m--)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            int x;
            cin >> x;
            int l = query(1, x);
            cout << l << endl;
            if (l != 0)
            {
                modify(1, l, l + x - 1, 1);
            }
        }
        else
        {
            int x, d;
            cin >> x >> d;
            modify(1, x, x + d - 1, -1);
        }
    }
    return 0;