【POJ1823】Hotel

2023-11-07 19:08

文章标签 hotel poj1823

本文主要是介绍【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;elset[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);}elseprintf("%d\n",t[1].Max);}return 0;
}