[USACO08FEB]Hotel G (区间最大子段和变式,线段树)

题意:

有n个房间(1-n),最开始所有的房间都是没有人住的,对你询问m次,每次有两个操作:

1,查询房间,输入一个x找1-n的房间中有连续长度为x的空房,输出连续x个空房中的最左的房间号,并且房间设置为有人,如果没有连续的就输出0
2.退房,输入x,y代表房间号x -> x + y - 1 退房, 即让房间为空

题解:

从题意上来看是一个区间的操作,所以可以往线段树方面去想.

使用线段树,那么考虑如何维护连续空房间的数量,对于连续的空房间其实就是类似找区间的最大子段和,我们能参考线段树区间最大子段和的维护值操作.所以也能确定线段树中的值存储每个点所代表区间的长度

区间最大子段和 [解释]

给出n个数,q次操作,每次修改值或者查找区间[L,R]内最大的连续子段和

对于树上的一个点使用 ls 和 rs 数组维护该点的左子树区间和右子树区间的最大连续字段和,使用tree数组维护ls和rs数组中的最大值加上左子树和右子树中的链接区间,所以建树过程为：

void build(ll rt, ll l, ll r){
    tree[rt] = ls[rt] = rs[rt] = len[rt] = r - l + 1;
    if(l == r) return;
    ll mid = (l + r) >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
}

对于题目中的查询操作,每次找该点到左树,左右树链接处和右树的最大连续字段和进行对比,如果左子树的连续子段大于则向左找,如果找了左子树没有找到则找左右子树链接部分,范围大于等于要找的话直接给出值，如果前面两个都没有找到则直接往右子树找

ll query(ll rt, ll l, ll r, ll v){
    push_up(rt);
    pt(rt);
    if(l == r) return l;
    ll mid = (l + r) >> 1;
    if(tree[rt << 1] >= v ) return query(rt << 1, l, mid, v); //符合则向左子树继续找
    else if(ls[rt << 1 | 1] + rs[rt << 1] >= v) return mid - rs[rt << 1] + 1; //符合直接返回最左点
    else return query(rt << 1 | 1, mid + 1, r, v); //上面都不符合则只可能在右子树中
}

题目中有两个修改操作,则对应的修改懒标记可以使用两个标签值来判断进行退房还是住房操作.(len 表示对应点的区间长度)

void push_up(ll x){ //懒标记
    if(lazy[x]){
        if(lazy[x] == 1){
            lazy[x << 1] = lazy[x];
            lazy[x << 1 | 1] = lazy[x];
            tree[x << 1] = ls[x << 1] = rs[x << 1] = 0;
            tree[x << 1 | 1] = ls[x << 1 | 1] = rs[x << 1 | 1] = 0;
            lazy[x] = 0;
        }else{
            lazy[x << 1] = lazy[x << 1| 1] = 2;
            tree[x << 1] = ls[x << 1] = rs[x << 1] = len[x << 1];
            tree[x << 1 | 1] = ls[x << 1 | 1] = rs[x << 1 | 1] = len[x << 1 | 1];
            lazy[x] = 0;
        }
    }
}
//修改
//tag =  1 清空 2添加 
void update(ll rt, ll l, ll r, ll L, ll R, ll tag){  
    push_up(rt);
    if(L <= l && r <= R){
        if(tag == 1) tree[rt] = ls[rt] = rs[rt] = 0;
        else tree[rt] = ls[rt] = rs[rt] = len[rt];
        lazy[rt] = tag;
        return;
    }
    ll mid = (l + r) >> 1;
    if(L <= mid) update(rt << 1, l, mid, L, R, tag);
    if(mid  < R) update(rt << 1 | 1, mid + 1, r, L, R, tag);
    pt(rt);
}

对于修改完后每次维护的ls,rs,tree数组可以分组讨论

ls：有两种情况
1. 该点的左子树房间全是空的,则该点ls = 左子树区间长度 + 右子树的ls
2. 该点的ls = 左子树的ls
rs: 有两种情况
1. 该点的右子树房间全是空的，则该点rs = 右子树区间长度 + 左子树rs
2. 该点的rs = 右子树的rs
tree: 直接取左子树右子树和链接处最大即可，链接处为左子树的rs + 右子树的ls

void pt(ll rt){
    if(tree[rt << 1] == len[rt << 1]){
        ls[rt] = ls[rt << 1 | 1] + len[rt << 1];
    }else ls[rt] = ls[rt << 1];
    if(tree[rt << 1 | 1] == len[rt << 1 | 1]){
        rs[rt] = rs[rt << 1] + len[rt << 1 | 1];
    }else rs[rt] = rs[rt << 1 | 1];
    tree[rt] = max(max(tree[rt << 1], tree[rt << 1 | 1]), ls[rt << 1 | 1] + rs[rt << 1]);
}

完整代码

ll tree[N], ls[N], rs[N], len[N];
ll lazy[N];
ll n, m;
void build(ll rt, ll l, ll r){
    tree[rt] = ls[rt] = rs[rt] = len[rt] = r - l + 1;
    if(l == r) return;
    ll mid = (l + r) >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
}
void pt(ll rt){
    if(tree[rt << 1] == len[rt << 1]){
        ls[rt] = ls[rt << 1 | 1] + len[rt << 1];
    }else ls[rt] = ls[rt << 1];
    if(tree[rt << 1 | 1] == len[rt << 1 | 1]){
        rs[rt] = rs[rt << 1] + len[rt << 1 | 1];
    }else rs[rt] = rs[rt << 1 | 1];
    tree[rt] = max(max(tree[rt << 1], tree[rt << 1 | 1]), ls[rt << 1 | 1] + rs[rt << 1]);
}
void push_up(ll x){
    if(lazy[x]){
        if(lazy[x] == 1){
            lazy[x << 1] = lazy[x];
            lazy[x << 1 | 1] = lazy[x];
            tree[x << 1] = ls[x << 1] = rs[x << 1] = 0;
            tree[x << 1 | 1] = ls[x << 1 | 1] = rs[x << 1 | 1] = 0;
            lazy[x] = 0;
        }else{
            lazy[x << 1] = lazy[x << 1| 1] = 2;
            tree[x << 1] = ls[x << 1] = rs[x << 1] = len[x << 1];
            tree[x << 1 | 1] = ls[x << 1 | 1] = rs[x << 1 | 1] = len[x << 1 | 1];
            lazy[x] = 0;
        }
    }
}
//tag =  1 清空 2添加
void update(ll rt, ll l, ll r, ll L, ll R, ll tag){
    push_up(rt);
    if(L <= l && r <= R){
        if(tag == 1) tree[rt] = ls[rt] = rs[rt] = 0;
        else tree[rt] = ls[rt] = rs[rt] = len[rt];
        lazy[rt] = tag;
        return;
    }
    ll mid = (l + r) >> 1;
    if(L <= mid) update(rt << 1, l, mid, L, R, tag);
    if(mid  < R) update(rt << 1 | 1, mid + 1, r, L, R, tag);
    pt(rt);
}

ll query(ll rt, ll l, ll r, ll v){
    push_up(rt);
    pt(rt);
    if(l == r) return l;
    ll mid = (l + r) >> 1;
    if(tree[rt << 1] >= v ) return query(rt << 1, l, mid, v);
    else if(ls[rt << 1 | 1] + rs[rt << 1] >= v) return mid - rs[rt << 1] + 1;
    else return query(rt << 1 | 1, mid + 1, r, v);
}
int main(){
    RLL2(n, m);
    build(1, 1, n);
    while(m --){
        ll s; RLL(s);
        if(s == 1){
            ll k; RLL(k);
            if(tree[1] >= k){
                ll ans = query(1, 1, n, k);
                PLN(ans);
                update(1, 1, n, ans, ans + k - 1, 1);
            }else PLN((ll)0);
        }else{
            ll l, r; RLL2(l, r);
            update(1, 1, n, l, l + r - 1, 2);
        }
    }
    return 0;
}

[USACO08FEB]Hotel G (区间最大子段和变式,线段树)

题意:

题解:

完整代码

感谢您的支持，我会继续努力的!