Description：

给一个序列，支持两个操作：

$1$ 、找一个最靠前的长度大于等于 $x$ 的空区间标记。

$2$ 、删除区间 $[l,r]$ 内的所有标记。

$1\le n \le 50000$

Solution：

看上去是个线段树，可以用线段树维护区间最长的空区间的长度，具体来说就是维护最长空前缀，最长空后缀和这个区间是否空三个标记然后合并和最大子段和类似但有点不同，然后每次在线段树上二分出最靠前的长度够大的区间标记，删除区间也可以打标记。 $tag=-1$ 无标记， $tag = 1$ 有覆盖标记， $tag=0$ 有清空标记。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 50010

#define INF 0x3f3f3f3f

struct node

{

    int lc,rc;

    int ls,rs,ms,s;

    int tag;

    node(){tag = -1;}

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void merge(int rt)

{

    int lc = t[rt].lc,rc = t[rt].rc;

    if(t[lc].s != -INF && t[rc].s != -INF)t[rt].s = t[lc].s + t[rc].s;

    else t[rt].s = -INF;

    if(t[lc].ls != -INF)t[rt].ls = max(t[lc].ls,t[lc].s + t[rc].ls);

    else t[rt].ls = -INF;

    if(t[rc].rs != -INF)t[rt].rs = max(t[rc].rs,t[rc].s + t[lc].rs);

    else t[rt].rs = -INF;

    t[rt].ms = max(t[lc].rs + t[rc].ls,max(t[lc].ms,t[rc].ms));

    return;

}

void build(int &rt,int l,int r)

{

    rt = newnode();

    t[rt].tag = -1;

    if(l == r)

    {

        t[rt].s = t[rt].ls = t[rt].rs = t[rt].ms = 1;

        return;

    }

    build(t[rt].lc,l,mid);

    build(t[rt].rc,mid + 1,r);

    merge(rt);

    return;

}

void pushdown(int rt,int l,int r)

{

    if(t[rt].tag == -1)return;

    int lc = t[rt].lc,rc = t[rt].rc;

    if(t[rt].tag == 1)

    {

        t[lc].s = t[lc].ls = t[lc].rs = t[lc].ms = mid - l + 1;

        t[rc].s = t[rc].ls = t[rc].rs = t[rc].ms = r - mid;

    }

    else

    {

        t[lc].s = t[lc].ls = t[lc].rs = t[lc].ms = -INF;

        t[rc].s = t[rc].ls = t[rc].rs = t[rc].ms = -INF;

    }

    t[lc].tag = t[rc].tag = t[rt].tag;

    t[rt].tag = -1;

    return;

}

void insert(int rt,int L,int R,int l,int r)

{

    if(L <= l && r <= R)

    {

        t[rt].tag = 1;

        t[rt].ms = t[rt].s = t[rt].ls = t[rt].rs = (r - l + 1);

        return;

    }

    pushdown(rt,l,r);

    if(L <= mid)insert(t[rt].lc,L,R,l,mid);

    if(R > mid)insert(t[rt].rc,L,R,mid + 1,r);

    merge(rt);

    return;

}

void remove(int rt,int L,int R,int l,int r)

{

    if(L <= l && r <= R)

    {

        t[rt].tag = 0;

        t[rt].ms = t[rt].s = t[rt].ls = t[rt].rs = -INF;

        return;

    }

    pushdown(rt,l,r);

    if(L <= mid)remove(t[rt].lc,L,R,l,mid);

    if(R > mid)remove(t[rt].rc,L,R,mid + 1,r);

    merge(rt);

    return;

}

int check(int rt,int len,int l,int r)

{

    if(l == r)

    {

        remove(root,l,l,1,n);

        return l;

    }

    if(t[rt].ms < len)return 0;

    pushdown(rt,l,r);

    if(t[t[rt].lc].ms >= len)return check(t[rt].lc,len,l,mid);

    if(t[t[rt].lc].rs + t[t[rt].rc].ls >= len)

    {

        int lef = mid - t[t[rt].lc].rs + 1;

        remove(root,lef,lef + len - 1,1,n);

        return lef;

    }

    return check(t[rt].rc,len,mid + 1,r);

}

int main()

{

    scanf("%d%d",&n,&m);

    build(root,1,n);

    int opt,x,y;

    for(int i = 1;i <= m;++i)

    {

        scanf("%d",&opt);

        if(opt == 1)

        {

            scanf("%d",&x);

            printf("%d\n",check(root,x,1,n));

        }

        else

        {

            scanf("%d%d",&x,&y);

            insert(root,x,x + y - 1,1,n);

        }

    }

    return 0;

}