# POJ 3667 Hotel

## 题解：

sub：最长连续子串；

pre：最长连续前缀

suf：最长连续后缀

0：区间全空；
1：区间全满；
-1：当前区间已初始化，不用向下更新

//
//  main.cpp
//  寒假训练
//
//  Created by Edwin on 2019/2/25.
//
#include<iostream>
#include<string.h>
#include<algorithm>
#include<string>
#include<math.h>
#include<stdio.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define maxn 100000+10
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<a;++i)
#define FORD(i,a,b) for(int i=a;i>=b;--i)
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
#define lson rt*2,l,m
#define rson rt*2+1,m+1,r
#define root 1,0,n-1
#define ls rt<<1
#define rs rt<<1|1
#define delf int m = l + r >> 1
int val[maxn],lazy[maxn<<2];
int sub[maxn<<2], pre[maxn<<2], suf[maxn<<2];//最长连续子串，最长前缀，最长后缀
void PushUp(int rt, int l, int r){
delf;
pre[rt] = pre[ls]; //更新pre
suf[rt] = suf[rs]; //更新suf
if(pre[rt]==m-l+1)pre[rt]+=pre[rs];
if(suf[rt]==r-m)suf[rt]+=suf[ls];
sub[rt] = max(sub[ls], max(sub[rs],suf[ls]+pre[rs])); //更新sub
}

void PushDown(int rt,int l,int r){
if(lazy[rt]==-1) return;
lazy[ls]=lazy[rs]=lazy[rt];
delf;
if(lazy[rt]){//全满
pre[ls]=suf[ls]=sub[ls]=0;
pre[rs]=suf[rs]=sub[rs]=0;
}
else{
pre[ls]=suf[ls]=sub[ls]=m-l+1;
pre[rs]=suf[rs]=sub[rs]=r-m;
}
lazy[rt]=-1;
}

void build(int rt, int l, int r){
lazy[rt]=-1;
sub[rt] = pre[rt] = suf[rt] = r-l+1;//初始化
if(l==r) return;
delf;
build(lson);
build(rson);
PushUp(rt, l, r);
}

void update(int ql, int qr,int v, int rt, int l, int r){
if(l == ql&&r==qr){
lazy[rt]=v;
if(v) sub[rt] = pre[rt] = suf[rt] = 0;
else sub[rt] = pre[rt] = suf[rt] = r-l+1;
return ;
}
delf;
PushDown(rt,l,r);
if(qr <= m) update(ql, qr, v , lson);
else if(ql>m) update(ql, qr, v , rson);
else update(ql, m, v , lson),update(m+1, qr, v , rson);
PushUp(rt, l, r);
}

int query(int len,int rt,int l,int r){
if(l==r) return l;
PushDown(rt,l,r);
delf;
if(sub[ls]>=len) return query(len,ls,l,m);//全在左
else if(suf[ls]+pre[rs]>=len) return m-suf[ls]+1;//横跨两边
else return query(len,rs,m+1,r);//全在右
}
int main(){
int n, m;
sc2(n,m);
build(1,1,n);
while(m--){
int ch;
sc(ch);
if(ch==1){
int len;
sc(len);
if(sub[1]<len) {printf("0\n");continue;}
int q=query(len,1,1,n);
pr(q);
update(q,q+len-1,1,1,1,n);
}
else{
int ql,qr;
sc2(ql,qr);
update(ql,ql+qr-1,0,1,1,n);
}
}
return 0;
}


0 评论