题解 2018寒假训练3 D.酒店
zhouwc
2018-02-25 09:37:31
问题 D: 酒店
时间限制: 1 Sec 内存限制: 128 MB
[提交][状态][讨论版]
题目描述
A城市有个超级大酒店，住房部只有一层，只向南，但房间有N个（编号1, 2 .. N）。刚开始所有房间都是空的，但酒店肯定会有人来住宿，有些房间就要被入住。但客人经常会问一个问题，最长连续的空房间是多少，因为客人想连续的住在一起。于是，有下列三个操作：
1 a b：表示从房间a开始连续b个房间，将被入住（不管有没有人已经入住）
2 a b：表示从房间a开始连续b个房间，将清空入住(不管有没有人入住)
3：表示询问当前最长连续的空房间是多少？
对于3的询问，输出相应答案。
输入
首先输入N和P, N如问题描述，P表示有多少个操作
然后输入P个操作
输出
对于第三种操作，输出相应答案
样例输入
12 10 3 1 2 3 1 9 4 3 2 2 1 3 2 9 2 3 2 3 2 3
样例输出
12 4 4 6 10
提示
【数据规模和约定】
3<=N<=16,000
3<=P<=200,000
题解
班长的代码与思路。fyk大佬的讲解与修改。
```cpp
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100005;
int n,m,op,l,r;
int mx[N],lmx[N],rmx[N],col[N];
void build(int l,int r,int id){
if(l==r){
mx[id]=lmx[id]=rmx[id]=1;
col[id]=1;
return;
}
int mid=(l+r)>>1;
build(l,mid,id<<1);
build(mid+1,r,id<<1|1);
mx[id]=lmx[id]=rmx[id]=r-l+1;
col[id]=1;
}
void update(int L,int R,int k,int l,int r,int id){
if(L<=l&&r<=R){
col[id]=k;
if(k==1)mx[id]=lmx[id]=rmx[id]=r-l+1;
else mx[id]=lmx[id]=rmx[id]=0;
return;
}
int mid=(l+r)>>1;
if(col[id]!=-1)col[id<<1]=col[id<<1|1]=col[id];
if(col[id]==1){
mx[id<<1]=lmx[id<<1]=rmx[id<<1]=mid-l+1;
mx[id<<1|1]=lmx[id<<1|1]=rmx[id<<1|1]=r-mid;
}
if(col[id]==0){
mx[id<<1]=lmx[id<<1]=rmx[id<<1]=0;
mx[id<<1|1]=lmx[id<<1|1]=rmx[id<<1|1]=0;
}
col[id]=-1;
if(L<=mid)update(L,R,k,l,mid,id<<1);
if(mid<R) update(L,R,k,mid+1,r,id<<1|1);
mx[id]=max(max(mx[id<<1],mx[id<<1|1]),rmx[id<<1]+lmx[id<<1|1]);
if(col[id<<1]==col[id<<1|1])col[id]=col[id<<1];
if(col[id<<1]==1)lmx[id]=mx[id<<1]+lmx[id<<1|1];
if(col[id<<1]==0)lmx[id]=0;
if(col[id<<1]==-1)lmx[id]=lmx[id<<1];
if(col[id<<1|1]==1)rmx[id]=rmx[id<<1]+mx[id<<1|1];
if(col[id<<1|1]==0)rmx[id]=0;
if(col[id<<1|1]==-1)rmx[id]=rmx[id<<1|1];
}
int main(){
scanf("%d%d",&n,&m);
build(1,n,1);
for(int i=1;i<=m;i++){
scanf("%d",&op);
if(op==3)printf("%d\n",mx[1]);
else{
scanf("%d%d",&l,&r);r=l+r-1;
update(l,r,op-1,1,n,1);
}
}
return 0;
}
```