学步园

10 6
1 3
1 3
1 3
1 3
2 5 5
1 6

1
4
7
0
5

开始用自己的想法写的。磨了一下午。终于各种测试样例都过了。但是交上去却wa了。无奈只有去网上参考网上的代码，发现和自己的思想几乎一样。只是更新父结点信息的方式不一样。由于时间关系没有纠结自己的代码。按照网上更新方法改了下。就A了。

思路：

既然要查询是否存在一个长为d的连续空区间，那么我们至少要记录对于每个区间而言，其中的最长的连续空区间是多大，这个用ma[](max all)表示。同时在查找的过程中，连续空区间有三种形式，在左子树，在右子树，或者横跨两棵子树。当然我们要优先找左子树，最后再找右子树，那么中间的这个横跨的怎么办呢？于是我们可以引入ml[](max left )表示一个区间从左边开始连续最长的区间是多少，mr[](max right)表示一个区间从右边开始连续最长的区间是多少，如果mr[left
son]+ml[right son]>=d，那么就说明存在这样一个横跨两棵子树的区间，由于我们知道左子树最右边点的坐标x，那么这个连续空区间的第一个位置自然就是x-mr[left son]+1。
查找功能实现了之后，剩下的就是染色了，如果是住进去就都染成1，如果是搬出来就都染成-1。
 此外，我们在染色之后只要更新父节点ma[]、ml[]、mr[]的状态的，这时对于父节点这个区间，最长的连续区间除了左子树中最长的和右子树中最长的，还要将横跨两棵子树的最长的连续区间也纳入考虑的范围。

更新时遇到匹配区间直接加lazy标记就行。下次路过时带下去就行。

详细见代码：

#include <iostream>
#include<string.h>
#include<stdio.h>
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define positive(a) ((a)>0?(a):-(a))
using namespace std;

const int maxn=50100;
int ml[maxn<<2],mr[maxn<<2],ma[maxn<<2];
int st[maxn<<2];
int n,m;
void btree(int L,int R,int k)//建树
{
    int ls,rs,mid;
    ma[k]=ml[k]=mr[k]=(R-L+1);//初始化。ma为区间内最大连续房间数。ml为区间左端最大连续房间数。mr为右端。。
    st[k]=0;//0表示无标记。1表示区间内房间全被占用。-1表示区间房间全空闲
    if(L==R)
        return;
    ls=k<<1;
    rs=k<<1|1;
    mid=(L+R)>>1;
    btree(L,mid,ls);
    btree(mid+1,R,rs);
}
void change(int L,int R,int k)//根据状态修改结点信息
{
    if(st[k]==1)//占用
        ml[k]=mr[k]=ma[k]=0;
    else
        ml[k]=mr[k]=ma[k]=R-L+1;
}
void pushdown(int L,int R,int k)//下传标记
{
    int ls,rs,mid;
    ls=k<<1;
    rs=k<<1|1;
    mid=(L+R)>>1;
    if(st[k]==1)//占用
    {
        st[ls]=st[rs]=1;
        ml[ls]=mr[ls]=ma[ls]=0;
        ml[rs]=mr[rs]=ma[rs]=0;
    }
    else
    {
        st[ls]=st[rs]=-1;
        ml[ls]=mr[ls]=ma[ls]=mid-L+1;
        ml[rs]=mr[rs]=ma[rs]=R-mid;
    }
    st[k]=0;
}
void check(int L,int R,int l,int r,int k,int s)
{
    int ls,rs,mid;

    if(l==L&&r==R)
    {
        st[k]=s;
        change(L,R,k);
        return;
    }
    ls=k<<1;
    rs=k<<1|1;
    mid=(L+R)>>1;
    if(st[k])
        pushdown(L,R,k);
    if(l>mid)
        check(mid+1,R,l,r,rs,s);
    else if(r<=mid)
        check(L,mid,l,r,ls,s);
    else
    {
        check(L,mid,l,mid,ls,s);
        check(mid+1,R,mid+1,r,rs,s);
    }
    ma[k]=MAX(ma[ls],ma[rs]);
    ma[k]=MAX(ma[k],mr[ls]+ml[rs]);//找到最大区间
    ml[k]=ml[ls];//最基本的值
    mr[k]=mr[rs];
    if(ma[ls]==mid-L+1)//若右区间全满
        ml[k]+=ml[rs];//可能变成的值
    if(ma[rs]==R-mid)
        mr[k]+=mr[ls];
    //printf("%d->%d ma:%d ml:%d mr:%d\n",L,R,ma[k],ml[k],mr[k]);
}
int qu(int L,int R,int k,int cost)
{
    int ls,rs,mid;
    if(cost>ma[k])
        return 0;
    if(L==R)
        return L;
    ls=k<<1;
    rs=k<<1|1;
    mid=(L+R)>>1;
    if(st[k])
        pushdown(L,R,k);
    if(cost<=ma[ls])//优先取左边编号
        return qu(L,mid,ls,cost);
    else if(cost<=mr[ls]+ml[rs])
        return mid-mr[ls]+1;
    else
        return qu(mid+1,R,rs,cost);
}
int main()
{
    int com,i,ans,x,d;

    while(~scanf("%d%d",&n,&m))
    {
        btree(1,n,1);
        for(i=1; i<=m; i++)
        {
            scanf("%d",&com);
            if(com==1)
            {
                scanf("%d",&d);
                ans=qu(1,n,1,d);
                printf("%d\n",ans);
                if(ans)
                    check(1,n,ans,ans+d-1,1,1);
            }
            else
            {
                scanf("%d%d",&x,&d);
                check(1,n,x,x+d-1,1,-1);
            }
        }
    }
    return 0;
}