BZOJ 1593/3050: [Usaco2008 Feb]Hotel – [线段树]


题目传送门(BZOJ)
>原文链接<

题解

线段树区间合并模板题, 稍复杂

设这样几个数组 : siz、lsiz、rsiz、len、laz

分别表示 区间最大连续长度从左开始的最大连续长度从右开始的区间最大连续长度区间总长度懒度标记

每个节点的siz就是两个儿子的siz和左儿子的rsiz+右儿子的lsiz\max

对于lsiz的维护,若左儿子的siz等于len,那么就是左儿子siz加右儿子lsiz,否则是左儿子的lsiz

对于rsiz的类似。

本题输入有小坑,一次退房的(x, y)是从xx+y-1

  对于每次查询,如果siz[root] ,那么直接输出0即可,否则的话以 siz[ls]>K ? rsiz[ls]+lsiz[rs]siz[rs] 的顺序选择递归,如果左子树不够大,而中间部分足够,那么我们可以直接返回ans

并从ans+query的区间范围对树进行修改, 区间覆盖然后pushUp即可.

代码

#include 
#include 
#include 
#include 
#define ls p<<1
#define rs p<<1|1
#define lson l, m, p<<1
#define rson m+1, r, p<<1|1
#define im int mid = (l+r) >> 1
using namespace std;
const int N = 410000;
int ans=0, n;
struct SegTree {
    int lsz[N<<2],  rsz[N<<2],  siz[N<<2],  laz[N<<2],  len[N<<2];
    void pushup(int p) {
        lsz[p]=(siz[ls]==len[ls]?len[ls]+lsz[rs]:lsz[ls]);
        rsz[p]=(siz[rs]==len[rs]?len[rs]+rsz[ls]:rsz[rs]);
        siz[p]=max(siz[ls], max(siz[rs], rsz[ls]+lsz[rs]));
    }
    void pushdown(int p) {
        if(laz[p]==1) {
            lsz[rs]=rsz[rs]=siz[rs]=lsz[ls]=rsz[ls]=siz[ls]=0;
            laz[ls]=laz[rs]=1;
        }
        else if(laz[p]==2) {
            lsz[rs]=rsz[rs]=siz[rs]=len[rs];
            lsz[ls]=rsz[ls]=siz[ls]=len[ls];
            laz[ls]=laz[rs]=2;
        }
        laz[p]=0;
    }
    void build(int l, int r, int p) {
        lsz[p]=rsz[p]=siz[p]=len[p]=r-l+1;
        if(l==r)return;
        im;
        build(l, mid, ls);
        build(mid+1, r, rs);
    }
    int query(int l, int r, int p, int x) {
        pushdown(p);
        if(l==r) return l;
        int m = (l+r)>>1;
        if(siz[ls]>=x) return query(lson, x);
        if(rsz[ls]+lsz[ls|1]>=x) return m-rsz[ls]+1;
        else return query(rson, x);
    }
    void change(int l, int r, int p, int x, int y, int c) {
        pushdown(p);
        if(x<=l&&y>=r) {
            if(c==1) siz[p]=lsz[p]=rsz[p]=0;
            else siz[p]=lsz[p]=rsz[p]=len[p];
            laz[p]=c;
            return;
        }
        im;
        if(x<=mid) 
            change(l, mid, ls, x, y, c);
        if(y>mid)
            change(mid+1, r, rs, x, y, c);
        pushup(p);
    }
}Tr;
int main() {
    int q;
    scanf("%d%d", &n, &q);
    Tr.build(1, n, 1);
    while (q--) {
        int opt, x, y, p;
        scanf("%d", &opt);
        if(opt==1) {
            scanf("%d", &x);
            if(Tr.siz[1]

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注