【POJ1823】Hotel

题目链接：http://poj.org/problem?id=1823
题意：
有三种操作

• 1 A M 表示从 A 到 A+M-1 住进M个人
• 2 A M 表示从 A 到 A+M-1 搬到M个人
• 3 表示查询这个hotel 连续的空房间有多少

题解：
区间合并问题
线段树维护从左端/右端/整段最多连续0的个数
col标记整段覆盖情况，-1表示全空，1表示全满，0表示不空不满
维护起来比较复杂，看代码吧

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define getmid int m=(t[rt].l+t[rt].r)>>1
#define LL long long
#define L(rt) (rt<<1)
#define R(rt) (rt<<1|1)

const int N=16050;
int n,m;

struct segtree
{
    int Max,lmax,rmax,l,r,col;
    //col 1->full -1->empty 0->not full not empty
}t[N<<2];

void Build(int l,int r,int rt)
{
    t[rt].l=l;
    t[rt].r=r;
    if(l==r)    return;
    int m=(l+r)>>1;
    Build(l,m,L(rt));
    Build(m+1,r,R(rt));
}

void Pushdown(int op,int rt)
{
    if(op==-1)
    {
        t[rt].col=0;
        t[L(rt)].col=op;
        t[L(rt)].Max=t[L(rt)].lmax=t[L(rt)].rmax=t[L(rt)].r-t[L(rt)].l+1;
        t[R(rt)].col=op;
        t[R(rt)].Max=t[R(rt)].lmax=t[R(rt)].rmax=t[R(rt)].r-t[R(rt)].l+1; 
    }
    else
    {
        t[rt].col=0;
        t[L(rt)].col=op;
        t[L(rt)].Max=t[L(rt)].lmax=t[L(rt)].rmax=0;
        t[R(rt)].col=op;
        t[R(rt)].Max=t[R(rt)].lmax=t[R(rt)].rmax=0; 
    }
}

void Update(int op,int L,int R,int rt)
{
    if(t[rt].l==L&&t[rt].r==R)
    {
        t[rt].col=op;
        if(op==1)
            t[rt].Max=t[rt].lmax=t[rt].rmax=0;
        else 
            t[rt].Max=t[rt].lmax=t[rt].rmax=t[rt].r-t[rt].l+1;
        return; 
    }
    if(t[rt].col==op) return;
    if(t[rt].col==-op)
        Pushdown(-op,rt);
    getmid;
    if(R<=m) Update(op,L,R,L(rt));
    else if(L>m) Update(op,L,R,R(rt));
    else
    {
        Update(op,L,m,L(rt));
        Update(op,m+1,R,R(rt)); 
    }

    if(t[L(rt)].col==-1)
        t[rt].lmax=t[L(rt)].Max+t[R(rt)].lmax;
    else
        t[rt].lmax=t[L(rt)].lmax;
    if(t[R(rt)].col==-1)
        t[rt].rmax=t[R(rt)].Max+t[L(rt)].rmax;
    else 
        t[rt].rmax=t[R(rt)].rmax;

    int mid=t[L(rt)].rmax+t[R(rt)].lmax;
    int a=max(t[rt].lmax,t[rt].rmax);
    int b=max(t[L(rt)].Max,t[R(rt)].Max);
    t[rt].Max=max(max(a,b),mid);
    if(t[L(rt)].col==t[R(rt)].col)
        t[rt].col=t[L(rt)].col;
}

int main()
{
    scanf("%d%d",&n,&m);
    Build(1,n,1);
    t[1].col=-1;
    t[1].Max=n;
    int a,b,c;
    while(m--)
    {
        scanf("%d",&c);
        if(c==1)
        {
            scanf("%d%d",&a,&b);
            Update(1,a,a+b-1,1);
        }
        else if(c==2)
        {
            scanf("%d%d",&a,&b);
            Update(-1,a,a+b-1,1);
        }
        else
            printf("%d\n",t[1].Max);
    }
    return 0;
}