POJ 3667 Hotel

Time Limit : 6000/3000ms (Java/Other)   Memory Limit : 131072/65536K (Java/Other)

题意:n个连续的房间,m个操作。
操作分两种,第一种以1 len形式给出,找到最左的能连续容下len个人的连续房间,并输出左端点的编号,如果找不到就输出0.
第二种以2 l len的形式给出,表示以l为起点的len个房间都清空。

题解:

咋一看,这道题和HDOJ3308 简直如出一辙,同样是维护三个区间:


sub:最长连续子串;


pre:最长连续前缀

suf:最长连续后缀
同时lazy数组有三个状态:
0:区间全空;
1:区间全满;
-1:当前区间已初始化,不用向下更新
同时注意一下PushUp的策略,详情请看代码

//
//  main.cpp
//  寒假训练
//
//  Created by Edwin on 2019/2/25.
//  Copyright © 2019 Edwiv. All rights reserved.
//
#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;
}

 

发表评论,支持MarkDown语法