800人的题目整整做了2个小时，而且还是参考别的解题报告，还需努力啊！

题目描述：

一个旅馆有n个房间，标号1到n，有两种操作：

1：来了k个人，让你在旅馆找连续的k个房间，使其中第一个房间号尽量小，输出它，如果不存在输出-1.

2：清空从i号房间开始的d个房间。

解题报告：

每个节点有

l,r           

lenl, lenr, lenmax         

idr, idmax  

flag 

八个数据块

l表示左边界，r：右边界

lenl：从最左边开始连续的空房间数。lenr：从最右边开始连续的空房间数。lenmax：最大的连续房间数（可能和上两个重复，仅仅是为了寻找最大）。

idr：和lenr对应，是从右开始连续房间最左边的编号。其实它就等于r - lenr + 1

idman：和lenmax对应，最大连续房间数最左边房间的编号。

flag:  1：表示这一段房间全满，0：表示全空，-1:其他情况。

插入于删除操作大体和平时的线段树方法一致。

主要是维护那8个数据的代码需要思考。

方法如下：

设插入（或者删除）的边界是a，b，当前节点编号是i。

1):如果遇到节点t[k].l == a && t[k].r == b
则说明当前区间需要进行操作，根据参数flag进行相应操作，返回；

2):否则，如果当前flag是0或者1，则对其两个孩子的flag向下传递。

其他数据维护：

如果左孩子是不是空的。那么i节点的左长度一定和做孩子的一样。

t[i].lenl = t[i * 2].lenr.

否则，就是左孩子的左长度（全部长度）加上右孩子左长度

t[i].lenl = t[i * 2].lenl + t[i * 2 + 1].lenl;

t[i].lenr也类似。

然后是t[i].lenmax。

除了要考虑t[2*i].lenr+t[2*i+1].lenl(左孩子和右孩子相连的部分），还需要分别考虑t[2*i].lenmax和t[2*i+1].lenmax

然后是查询：

假设查询长度是d

先看节点i的左连续1区间lenr，如果满足，直接返回左端点t[i].l；
如果不满足，查找中间连续1区间lenmax，如果lenmax==d，则返回记录的起始点idmax，如果lenmax< d或者此时已到达叶节点，则返回-1，查找失败。
仍需要单独考虑lenmax > d的情况，因为lenmax记录是当前区间最长连续1区间的长度，并不代表这是我们要查找的答案，因为可能区间里仍存在长度符合，而起始点更小的连续1区间，因此我们先进入左子树进行查找，如果失败，接着判断中间连续序列t[2*i].lenr + t[2*i+1].lenl >= d是否成立，成立则返回此序列起始点，如果不成立，进入右子树进行查找，返回结果。
结束

代码如下：

#include<iostream>
using namespace std;
#define size 50004
struct MyTree
{
    int l, r;
    int lenl, lenr, lenmax;
    int idr, idmax;
    int flag; //1 满 0 空 -1其他
}t[size * 3];
void change(bool del, int i)
{
    if (del)
    {
        t[i].lenl = t[i].lenr = t[i].lenmax = t[i].r - t[i].l + 1;
        t[i].idr = t[i].idmax = t[i].l;
        t[i].flag = 0;
    }
    else
    {
        t[i].lenl = t[i].lenr = t[i].lenmax = 0;
        t[i].idr = t[i].idmax = t[i].r + 1;
        t[i].flag = 1;
    }
}
void build(int a, int b, int i)
{
    t[i].l = a;t[i].r = b;
    t[i].lenl = t[i].lenr = t[i].lenmax = b - a + 1;
    t[i].idr = t[i].idmax = a;
    t[i].flag = 0;
    if (b - a)
    {
        build(a, (a + b) / 2, i * 2);
        build((a + b) / 2 + 1, b, i * 2 + 1);
    }
}
void insert(int a, int b, bool del, int i)
{
    if (t[i].l == a && t[i].r == b)
        change(del, i);
    else // t[i].l <= a <= b <= t[i].r => t[i]一定有左右子树
    {
        int mid = (t[i].l + t[i].r) / 2;
        if (t[i].flag == 1) change(0, i * 2), change(0, i * 2 + 1);
        else if (t[i].flag == 0) change(1, i * 2), change(1, i * 2 + 1);
        t[i].flag = -1;
        if (b <= mid)
            insert(a, b, del, i * 2);
        else if (a > mid)
            insert(a, b, del, i * 2 + 1);
        else
            insert(a, mid, del, i * 2), insert(mid + 1, b, del, i * 2 + 1);
        if (del)
        {
            if (t[i * 2].lenl == t[i * 2].r - t[i * 2].l + 1)
                t[i].lenl = t[i * 2].lenl + t[i * 2 + 1].lenl;
            else
                t[i].lenl = t[i * 2].lenl;
            if (t[i * 2 + 1].lenr == t[i * 2 + 1].r - t[i * 2 + 1].l + 1)
                t[i].lenr = t[i * 2 + 1].lenr + t[i * 2].lenr, t[i].idr = t[i * 2].idr;
            else
                t[i].lenr = t[i * 2 + 1].lenr, t[i].idr = t[i * 2 + 1].idr;
        }
        else
        {
            if (a <= t[i].lenl + t[i].l - 1)
                t[i].lenl = (a - 1) - t[i].l + 1;
            if (b >= t[i].idr)
            {
                t[i].lenr = t[i].r - (b + 1) + 1;
                t[i].idr = b + 1;
            }
        }
        t[i].lenmax = t[i].lenl;t[i].idmax = t[i].l;
        if (t[i * 2].lenmax > t[i].lenmax)
            t[i].lenmax = t[i * 2].lenmax, t[i].idmax = t[i * 2].idmax;
        if (t[i * 2].lenr + t[i * 2 + 1].lenl > t[i].lenmax)
            t[i].lenmax = t[i * 2].lenr + t[i * 2 + 1].lenl, t[i].idmax = t[i * 2].idr;
        if (t[i * 2 + 1].lenmax > t[i].lenmax)
            t[i].lenmax = t[i * 2 + 1].lenmax, t[i].idmax = t[i * 2 + 1].idmax;
    }
}
int ans;
void query(int i, int len)
{
    if (t[i].flag == 1) change(0, i * 2), change(0, i * 2 + 1);
    else if (t[i].flag == 0) change(1, i * 2), change(1, i * 2 + 1);
    if (t[i].l == t[i].r)
    {
        if (t[i].lenmax == len)
            ans = t[i].l;
    }
    else if (t[i].lenl >= len)
        ans = t[i].l;
    else if (t[i].lenmax == len)
        ans = t[i].idmax;
    else if (t[i].lenmax < len)
        ans = -1;
    else if (t[i].lenmax > len)
    {
        query(i * 2, len);
        if (ans == -1 && t[i * 2].lenr + t[i * 2 + 1].lenl >= len)
            ans = t[i * 2].idr;
        if (ans == -1)
            query(i * 2 + 1, len);
    }
}
int n, m, state, len, d1, d2;
int main()
{
    scanf("%d%d", &n, &m);
    build(1, n, 1);
    for(int i = 0; i < m; i++)
    {
        scanf("%d", &state);
        if (state == 1)
        {
            scanf("%d", &len);
            ans = -1;query(1, len);
            if (ans == -1) printf("0\n");
            else
            {
                printf("%d\n", ans);
                insert(ans, ans + len - 1, 0, 1);
            }
        }
        else
        {
            scanf("%d%d", &d1, &d2);
            insert(d1, d1 + d2 - 1, 1, 1);
        }
    }
    return 0;
}