POJ 1823 Hotel 线段树 + lazy标签
题意：有一些房间，对这些房间有三种操作，一是一段连续的房间住人，二是一段连续的房间变空，三是询问这些房间中最长的一段连续的房间是多长。思路：明显是线段树的题目，中间用到了lazy思想，好题中的好题啊。挺难的一道题目，需要好好思考。这道题的关键之处在于，用lazy向下更新完之后，父结点的信息还需要根据子结点的信息来改变。也就是说，同时需要从下向上更新。
代码：
[cpp]
#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);
