Mayflyyh
Mayflyyh
MayFlyyh's Blog
BZOJ 1593[Usaco2008 Feb]Hotel 旅馆

参考样例,第一行输入n,m ,n代表有n个房间,编号为1—n,开始都为空房,m表示以下有m行操作,以下 每行先输入一个数 i ,表示一种操作:

若i为1,表示查询房间,再输入一个数x,表示在1–n 房间中找到长度为x的连续空房,输出连续x个房间中左端的房间号,尽量让这个房间号最小,若找不到长度为x的连续空房,输出0。

若i为2,表示退房,再输入两个数 x,y 代表 房间号 x—x+y-1 退房,即让房间为空。

线段树代码题

维护区间最左面的连续1的长度,最右边连续1的长度,以及区间内连续1最长的长度

线段树维护左边和右边是为了为父节点合并
(上传) 做铺垫

然后 就是查找的时候需要自己想想

如果当前区间的左儿子中有连续x的1,就返回左儿子的答案

如果左儿子最右边连续的与右儿子最左边连续之和大于x,就返回答案减去左儿子的大小+mid+1(满足尽量靠左)

如果还不行就查右儿子

再不行返回0

CODE:

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
const int N = 100110;
int sum[N<<2],cov[N<<2];
int ls[N<<2],rs[N<<2],mx[N<<2];//全空为1 
inline int pushup(int cur,int x){
    sum[cur]=sum[cur<<1]+sum[cur<<1|1]; 
    if(sum[cur<<1]==(x+1>>1)) ls[cur]=sum[cur<<1]+ls[cur<<1|1];
    else ls[cur]=ls[cur<<1];
    if(sum[cur<<1|1]==(x>>1)) rs[cur]=sum[cur<<1|1]+rs[cur<<1];
    else rs[cur]=rs[cur<<1|1];
    mx[cur]=std::max(mx[cur<<1],std::max(mx[cur<<1|1],ls[cur<<1|1]+rs[cur<<1]));
}
inline int pushdown(int cur,int x){
    if(cov[cur]!=-1){
        sum[cur<<1]=cov[cur]*(x+1>>1);
        sum[cur<<1|1]=cov[cur]*(x>>1);
        cov[cur<<1]=cov[cur];
        cov[cur<<1|1]=cov[cur];
        cov[cur]=-1;
        if(sum[cur<<1]) mx[cur<<1]=ls[cur<<1]=rs[cur<<1]=(x+1)>>1;
        else mx[cur<<1]=ls[cur<<1]=rs[cur<<1]=0;
        if(sum[cur<<1|1]) mx[cur<<1|1]=ls[cur<<1|1]=rs[cur<<1|1]=x>>1;
        else mx[cur<<1|1]=ls[cur<<1|1]=rs[cur<<1|1]=0;
    }
}
inline int build(int l,int r,int cur){
    cov[cur]=-1;
    if(l==r){
        sum[cur]=ls[cur]=rs[cur]=mx[cur]=1;

        return 0;
    }
    int mid=l+r>>1;
    build(l,mid,cur<<1);
    build(mid+1,r,cur<<1|1);
    pushup(cur,r-l+1);
    return 0;
}
inline int ask(int l,int r,int cur,int x){
    pushdown(cur,r-l+1);
    int mid=l+r>>1;

    if(l==r){
        if(sum[cur]==0) return 0;
        return 1;
    }
    if(mx[cur<<1]>=x) return ask(l,mid,cur<<1,x);
    if(rs[cur<<1]+ls[cur<<1|1]>=x){
        return mid-rs[cur<<1]+1;
    }
    if(mx[cur<<1|1]>=x)return ask(mid+1,r,cur<<1|1,x);
    else return 0;
}
inline int change(int l,int r,int L,int R,int cur,int x){
    if(L<=l&&r<=R){
        sum[cur]=rs[cur]=ls[cur]=mx[cur]=x*(r-l+1);
        cov[cur]=x;
        return 0;
    }
    pushdown(cur,r-l+1);
    int mid = l+r>>1;
    if(L<=mid) change(l,mid,L,R,cur<<1,x);
    if(R>mid) change(mid+1,r,L,R,cur<<1|1,x);
    pushup(cur,r-l+1);
    return 0;
}
int n,m;
int main (){
    scanf("%d %d",&n,&m);
    build(1,n,1);
    while(m--){
        int od,l,r,x;
        scanf("%d",&od);
        if(od==1){
            scanf("%d",&x);
            int s=ask(1,n,1,x);

            printf("%d\n",s);
            if(s==0) continue;
            change(1,n,s,s+x-1,1,0);

        }
        if(od==2){
            scanf("%d %d",&l,&r);
            change(1,n,l,l+r-1,1,1);
        }
    }
    return 0;
}
本文链接:http://www.mayflyyh.com/archives/232
知识共享许可协议
本文采用CC BY-NC-SA 3.0进行许可。
首页      线段树      BZOJ 1593[Usaco2008 Feb]Hotel 旅馆
http://0.gravatar.com/avatar/6cc3a2831375e487976e09c80dfcb52e?s=256&d=monsterid&r=g

MayFlyyh

文章作者

Oier

发表评论

textsms
account_circle
email

Captcha Code

MayFlyyh's Blog

BZOJ 1593[Usaco2008 Feb]Hotel 旅馆
参考样例,第一行输入n,m ,n代表有n个房间,编号为1---n,开始都为空房,m表示以下有m行操作,以下 每行先输入一个数 i ,表示一种操作: 若i为1,表示查询房间,再输入一个数x,…
扫描二维码继续阅读
2018-06-16