http://poj.org/problem?id=3667
题意：
有n个连续的房间，m个操作，共有两种：
1 num 询问是不是有连续长度为num的空房间，若有，输出连续房间的最左边端点。
2 st num 将 [st,st+num-1]的房间清空。
本来想自己敲出这道题，敲到查询的时候没有思路，最后看解题报告，然后自己敲，一直没找到错误。。重敲一遍终于过了。。这道题是很经典的线段树问题。值得好好思考。
思路：
询问区间中满足条件的连续最长区间通常属于区间合并问题。
节点增加4个域，lx:从区间左边数连续空房间的数目。rx:从区间右边数连续空房间的数目。ax:该区间中连续空房间的总数目
col:记录该区间住人的状态，1表示全住满，0表示全空，-1表示有可以住的房间。
查询是否有连续空房间数目num的时候，先查询左边，当tree[v].lx >= num的时候递归左区间；再查询中间，当tree[v*2].lx +tree[v*2+1].rx >= num直接返回最左边端点；最后查询右边，当tree[v].rx>=num递归右区间。col记录该区间的状态，利用了Lazy思想，即当tree[v].col == 1或tree[v].col == 0 时（房间全住满或全不住的情况），要先把这个状态传递到左右子树，并把这个区间的col置为-1。
更新区间[st,st+num-1],即将该区间全置为空或置为满的时候，要先把区间的状态（全空或全满）传递给左右子树，然后递归，最后再把左右子树的状态更新上来，因为子树状态改变，父亲状态肯定也会改变。这个切记不要遗漏。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int maxn = 50005;
int flag;
struct line
{
int l,r;
int lx,rx,ax;//lx:从左边起连续空房间数目，rx:从右边起连续空房间数目,ax:整个区间中连续空房间数目最大值
int col;//col为1表示该区间全满，0表示全空，-1表示有房间可以住
}tree[maxn<<2];
void build(int v, int l, int r)
{
tree[v].l = l;
tree[v].r = r;
tree[v].col = 0; //初始化为空
tree[v].lx = tree[v].rx = tree[v].ax = r-l+1;
if(l == r)
return;
int mid = (l+r)>>1;
build(v*2,l,mid);
build(v*2+1,mid+1,r);
}
int query(int v, int num)
{
if(tree[v].lx == num && tree[v].r-tree[v].l+1 == num)
return tree[v].l;//如果该区间空房间数目与所需相等，直接返回
if(tree[v].ax >= num)//该区间最大连续空房间数目大于所需，要包括三种情况
{
if(tree[v].col != -1)//状态传递给左右子树
{
tree[v*2].col = tree[v*2+1].col = tree[v].col;
if(tree[v].col == 1)//1为全满
{
tree[v*2].lx = tree[v*2].rx = tree[v*2].ax = 0;
tree[v*2+1].lx = tree[v*2+1].rx = tree[v*2+1].ax = 0;
}
else if(tree[v].col == 0)//0为全空
{
tree[v*2].lx = tree[v*2].rx = tree[v*2].ax = tree[v*2].r-tree[v*2].l+1;
tree[v*2+1].lx = tree[v*2+1].rx = tree[v*2+1].ax = tree[v*2+1].r-tree[v*2+1].l+1;
}
tree[v].col = -1;//自己区间置为-1
}
if(tree[v*2].ax >= num)//左边连续房间数目大于所需，递归左区间
return query(v*2,num);
if(tree[v*2].rx+tree[v*2+1].lx >= num)//中间连续房间数目大于所需，返回左边端点
return tree[v*2].r-tree[v*2].rx+1;
if(tree[v*2+1].ax >= num)//右边连续空房间数目大于所需，递归右区间
return query(v*2+1,num);
}
return 0;
}
void update(int v, int l, int r)//更新[l,r]区间
{
if(tree[v].l == l && tree[v].r == r)//恰好是要更新区间，直接修改该区间状态
{
if(!flag)//flag为0表示表示全空
tree[v].lx = tree[v].rx = tree[v].ax = r-l+1;
else//为1表示全满
tree[v].lx = tree[v].rx = tree[v].ax = 0;
tree[v].col = flag;
return;
}
int mid = (tree[v].l+tree[v].r)>>1;
if(tree[v].col != -1)//状态传递给左右子树
{
tree[v*2].col=tree[v*2+1].col=tree[v].col;
if(tree[v].col == 1)
{
tree[v*2].lx=tree[v*2].rx=tree[v*2].ax=0;
tree[v*2+1].lx=tree[v*2+1].rx=tree[v*2+1].ax=0;
}
else if(tree[v].col == 0)
{
tree[v*2].lx=tree[v*2].rx=tree[v*2].ax=tree[v*2].r-tree[v*2].l+1;
tree[v*2+1].lx=tree[v*2+1].rx=tree[v*2+1].ax=tree[v*2+1].r-tree[v*2+1].l+1;
}
tree[v].col=-1;
}
if(r<=mid)
update(v*2,l,r);
else if(l > mid)
update(v*2+1,l,r);
else
{
update(v*2,l,mid);
update(v*2+1,mid+1,r);
}
//更新子区间以后，还要up上来，即更新到父节点，求父节点的lx,rx,ax,col.
if(tree[v*2].col==0)
tree[v].lx=tree[v*2].ax+tree[v*2+1].lx;
else tree[v].lx = tree[v*2].lx;
if(tree[v*2+1].col==0)
tree[v].rx=tree[v*2+1].ax+tree[v*2].rx;
else tree[v].rx=tree[v*2+1].rx;
tree[v].ax = max(tree[v*2].ax,tree[v*2+1].ax);
tree[v].ax = max(max(tree[v].ax,tree[v*2].rx+tree[v*2+1].lx),max(tree[v].lx,tree[v].rx));
if(tree[v].ax == tree[v].r-tree[v].l+1)
tree[v].col=0;
else if(tree[v].ax==0)
tree[v].col=1;
else tree[v].col=-1;
}
int main()
{
int n,m,x,num,st;
scanf("%d %d",&n,&m);
build(1,1,n);
while(m--)
{
scanf("%d",&x);
if(x == 1)
{
scanf("%d",&num);
st = query(1,num);
printf("%d\n",st);
if(st)
{
flag = 1;
update(1,st,st+num-1);
}
}
else
{
flag = 0;
scanf("%d %d",&st,&num);
update(1,st,st+num-1);
}
}
return 0;
}