题意：有两种操作
1，从左往右找一个区间是 D 的连续序列，然后覆盖，返回区间最前面的数，如果没有输出0
2， 释放从L开始连续D的区间
分析：就是从左往右查找一个D的连续区间，可以使用三个值操作lsum，rsum，sum，分别是从左往右的最大连续值，从右往左的最大连续值，整个区间的最大连续区间，与（I - Tunnel Warfare - hdu 1540）有些类似，不过更新时候是不一样的，这个sum单纯的保存最大连续区间
***********************************************************************
#include<algorithm>
#include<stdio.h>
using namespace std; #define lson r<<1
#define rson r<<1|1 const int MAXN = 1e5+; struct segmentTree
{///分别代表左边的最大连续区间，右边的最大连续区间，最大连续区间
int L, R, lsum, rsum, sum;
int op;///op等于 0 的时候不操作，等于 1 的时候房间占用，2 释放
int len(){return R-L+;}
int mid(){return (L+R)>>;}
}a[MAXN<<]; void pushDown(int r)
{
if(a[r].L != a[r].R && a[r].op)
{
a[lson].lsum = a[lson].rsum = a[lson].sum = (a[r].op == ? : a[lson].len());
a[rson].lsum = a[rson].rsum = a[rson].sum = (a[r].op == ? : a[rson].len()); a[lson].op = a[rson].op = a[r].op;
a[r].op = ;
}
}
void pushUp(int r)
{///一定要注意先把上层更新，才能进行合并操作
a[r].lsum = a[lson].lsum, a[r].rsum = a[rson].rsum; if(a[lson].lsum == a[lson].len())
a[r].lsum += a[rson].lsum;
if(a[rson].rsum == a[rson].len())
a[r].rsum += a[lson].rsum; a[r].sum = max(a[lson].sum, max(a[rson].sum, a[lson].rsum+a[rson].lsum));
}
void Build(int r, int L, int R)
{
a[r].L = L, a[r].R = R, a[r].op = ;
a[r].lsum = a[r].rsum = a[r].sum = a[r].len(); if(L == R)return ; Build(lson, L, a[r].mid());
Build(rson, a[r].mid()+, R);
}
void upDate(int r, int L, int R, int op)
{
if(a[r].L==L && a[r].R==R)
{///等于1房间完全被占用，那么剩余就是0，否则全部释放
a[r].lsum=a[r].rsum=a[r].sum = (op==? : a[r].len());
a[r].op = op; return ;
}
pushDown(r); if(R <= a[r].mid())
upDate(lson, L, R, op);
else if(L > a[r].mid())
upDate(rson, L, R, op);
else
{
upDate(lson, L, a[r].mid(), op);
upDate(rson, a[r].mid()+, R, op);
} pushUp(r);///向上更新父节点，只有下层改变值得时候需要这个操作
}
int Query(int r, int e)
{///判断原则，从左往右，找到最靠左的能够放下e的连续区间 pushDown(r); if( a[r].lsum >= e)return a[r].L;///判断最前面是否足够
if( a[lson].sum >= e )return Query(lson, e);///左子树够的话去左子树
if( a[lson].rsum +a[rson].lsum >= e )///判断中间是否足够
return a[lson].R - a[lson].rsum + ;
return Query(rson, e);///只能去右子树
} int main()
{
int N, M, L, R, op; while(scanf("%d%d", &N, &M) != EOF)
{
Build(, , N); while(M--)
{
scanf("%d", &op); if(op == )
{
scanf("%d", &R); if(R > a[].sum)///没有能放下的连续区间
printf("0\n");
else
{ L = Query(, R);
R = L+R-;///求出来右端
printf("%d\n", L);
upDate(, L, R, );
}
}
else
{
scanf("%d%d", &L, &R);
upDate(, L, L+R-, );
}
}
} return ; }