学步园

来源：http://poj.org/problem?id=1823

题意：有一些房间，对这些房间有三种操作，一是一段连续的房间住人，二是一段连续的房间变空，三是询问这些房间中最长的一段连续的房间是多长。

思路：明显是线段树的题目，中间用到了lazy思想，好题中的好题啊。挺难的一道题目，需要好好思考。这道题的关键之处在于，用lazy向下更新完之后，父结点的信息还需要根据子结点的信息来改变。也就是说，同时需要从下向上更新。

代码：

#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;

const int N = 16050;
struct tree
{
	int lp,rp,llen,rlen,mlen,flag;
	int getmid()
	{
	    return (lp + rp) / 2;
	}
}tt[N * 4];
void built_tree(int lp,int rp,int pos)
{
	tt[pos].lp = lp;
	tt[pos].rp = rp;
	tt[pos].flag = 0;
	if(lp == rp)
	{
	    tt[pos].llen = tt[pos].rlen = tt[pos].mlen = 1;
		return;
	}
	int mmid = tt[pos].getmid();
	built_tree(lp,mmid,pos*2);
	built_tree(mmid+1,rp,pos*2+1);
	tt[pos].llen = tt[pos].rlen = tt[pos].mlen = tt[pos*2].mlen + tt[pos*2+1].mlen;
}
int max(int a,int b)
{
	return a > b ? a : b;
}
void update(int pos)
{
	if(!tt[pos*2].flag)
		tt[pos].llen = tt[pos*2].mlen + tt[pos*2+1].llen;
	else
		tt[pos].llen = tt[pos*2].llen;
	if(!tt[pos*2+1].flag)
		tt[pos].rlen = tt[pos*2].rlen + tt[pos*2+1].mlen;
	else
		tt[pos].rlen = tt[pos*2+1].rlen;
	int max1 = max(tt[pos].llen,tt[pos].rlen);
	int max2 = tt[pos*2].rlen + tt[pos*2+1].llen;
	int max3 = max(tt[pos*2].mlen,tt[pos*2+1].mlen);
	tt[pos].mlen = max(max1,max(max2,max3));
	if(tt[pos*2].flag == tt[pos*2+1].flag)
		tt[pos].flag = tt[pos*2].flag;
}
void insert(int lp,int rp,int pos)
{
	if(tt[pos].lp == lp && tt[pos].rp == rp)
	{
	    tt[pos].flag = 2;
		tt[pos].llen = tt[pos].rlen = tt[pos].mlen = 0;
		return;
	}
	if(!tt[pos].flag)
	{
	    tt[pos].flag = 1;
		tt[pos*2].flag = tt[pos*2+1].flag = 0;
		tt[pos*2].llen = tt[pos*2].rlen = tt[pos*2].mlen = tt[pos*2].rp - tt[pos*2].lp + 1;
		tt[pos*2+1].llen = tt[pos*2+1].rlen = tt[pos*2+1].mlen = tt[pos*2+1].rp - tt[pos*2+1].lp + 1;
	}
	int mmid = tt[pos].getmid();
	if(rp <= mmid)
	{
	    insert(lp,rp,pos*2);
	}
	else if(lp > mmid)
	{
	    insert(lp,rp,pos*2+1);
	}
	else
	{
	   insert(lp,mmid,pos*2);
	   insert(mmid+1,rp,pos*2+1);
	}
	update(pos);
}
void rem(int lp,int rp,int pos)
{
	if(tt[pos].lp == lp && tt[pos].rp == rp)
	{
	    tt[pos].flag = 0;
		tt[pos].llen = tt[pos].rlen = tt[pos].mlen = tt[pos].rp - tt[pos].lp + 1;
		return;
	}
	if(tt[pos].flag == 2)
	{
	    tt[pos].flag = 1;
		tt[pos*2].flag = tt[pos*2+1].flag = 2;
		tt[pos*2].llen = tt[pos*2].rlen = tt[pos*2].mlen = 0;
		tt[pos*2+1].llen = tt[pos*2+1].rlen = tt[pos*2+1].mlen = 0;
	}
	int mmid = tt[pos].getmid();
	if(rp <= mmid)
		rem(lp,rp,pos*2);
	else if(lp > mmid)
		rem(lp,rp,pos*2+1);
	else
	{
	    rem(lp,mmid,pos*2);
		rem(mmid+1,rp,pos*2+1);
	}
	update(pos);
}
int main()
{
	//freopen("1.txt","r",stdin);
	int n,m;
	while(scanf("%d%d",&n,&m) != EOF)
	{
	    int id,x,y;
		built_tree(1,n,1);
		while(m--)
		{
		    scanf("%d",&id);
			if(id == 3)
				printf("%d\n",tt[1].mlen);
			else if(id == 1)
			{
			    scanf("%d%d",&x,&y);
				insert(x,x+y-1,1);
			}
			else
			{
			    scanf("%d%d",&x,&y);
				rem(x,x+y-1,1);
			}
		}
	}
	return 0;
}