[lnsyoj336/luoguP2894/USACO08FEB]Hotel

标签：子串 int Hotel tree len 区间 USACO08FEB lnsyoj336 llen

题意

原题链接
给定只包含\(0\)和\(1\)的序列\(a\)，支持两种操作：

查询\(a\)中最靠左的连续\(x\)个元素均为\(0\)的子串，输出子串的左端点，并将这个子串的所有元素置为\(1\)
将\(a\)中以\(x\)开始，长度为\(d\)的子串的所有元素置为\(0\)
初始时\(a\)的所有值都为\(0\)

sol

区间修改，区间查询，考虑线段树
每个节点需要记录\(5\)个值：

区间长度（便于更新节点信息）\(sze\)
区间内最长的连续\(0\)子串长度 \(len\)
区间内包含左端点的最长的连续\(0\)子串长度 \(llen\)
区间内包含右端点的最长的连续\(0\)子串长度 \(rlen\)
懒惰标记（\(0\)表示空标记，\(1\)表示区间所有元素改为\(1\)，\(2\)表示区间所有元素改为\(0\)) \(lazytag\)

PUSHUP操作

\(sze\)可以直接相加；\(len\)可以取左右儿子的\(len\)和左儿子的\(rlen\)与右儿子的\(llen\)之和中的最大值（想一想，为什么）
对于\(llen\)：

若左儿子的\(llen\)与其\(sze\)等长，说明左儿子全部为\(0\)，\(llen=lson.llen + rson.llen\)
否则说明左儿子中存在\(1\)，\(llen=lson.llen\)
\(rlen\)同理
代码如下

void pushup(int u){
    tree[u].sze = tree[u << 1].sze + tree[u << 1 | 1].sze;
    tree[u].len = max(tree[u << 1].len, tree[u << 1 | 1].len);
    tree[u].len = max(tree[u].len, tree[u << 1].rlen + tree[u << 1 | 1].llen);
    if (tree[u << 1].sze == tree[u << 1].llen) tree[u].llen = tree[u << 1].len + tree[u << 1 | 1].llen;
    else tree[u].llen = tree[u << 1].llen;
    if (tree[u << 1 | 1].sze == tree[u << 1 | 1].rlen) tree[u].rlen = tree[u << 1].rlen + tree[u << 1 | 1].len;
    else tree[u].rlen = tree[u << 1 | 1].rlen;
}

PUSHDOWN操作（懒惰标记下传）

若\(lazytag\)为\(0\)，则无需操作，同时不应下传，因为如果将其下传，其左右儿子原有的\(lazytag\)会被删除
若\(lazytag\)为\(1\)，则将左右儿子的\(len\)，\(rlen\)，\(llen\)都应置为\(0\)，因为区间内的所有元素都被修改为了\(1\)，不存在\(0\)
若\(lazytag\)为\(2\)，则将左右儿子的\(len\)，\(rlen\)，\(llen\)都应置为其\(sze\)，因为区间内的所有元素都被修改为了\(0\)，最大的连续子串即为其区间长度
代码见下

void pushdown(int u){
    if (!lazytag[u]) return ;
    if (lazytag[u] == 1) {
        tree[u << 1].len = tree[u << 1].rlen = tree[u << 1].llen = 0;
        tree[u << 1 | 1].len = tree[u << 1 | 1].rlen = tree[u << 1 | 1].llen = 0;
    }
    if (lazytag[u] == 2) {
        tree[u << 1].len = tree[u << 1].rlen = tree[u << 1].llen = tree[u << 1].sze;
        tree[u << 1 | 1].len = tree[u << 1 | 1].rlen = tree[u << 1 | 1].llen = tree[u << 1 | 1].sze;
    }
    lazytag[u << 1] = lazytag[u << 1 | 1] = lazytag[u];
    lazytag[u] = 0;
}

UPDATE操作

与正常线段树区间UPDATE操作一致，当被查询区间覆盖当前区间时，与PUSHDOWN操作相同
代码见下

void update(int u, int l, int r, int L, int R, int val){
    if (L <= l && r <= R){
        lazytag[u] = val;
        if (val == 1) tree[u].len = tree[u].rlen = tree[u].llen = 0;
        else if (val == 2) tree[u].len = tree[u].rlen = tree[u].llen = tree[u].sze;
        return ;
    }
    pushdown(u);
    int mid = l + r >> 1;
    if (L <= mid) update(u << 1, l, mid, L, R, val);
    if (R > mid) update(u << 1 | 1, mid + 1, r, L, R, val);
    pushup(u);
}

QUERY操作

如果遍历到的区间只有一个元素，即\(l=r\)，说明该区间就是满足要求的子串的左端点，直接返回即可
由于题目要求输出最靠左的满足要求的答案，因此应按照从左到右的顺序判断

若答案在左儿子中，即\(lson.len\ge x\)，则遍历左儿子
若答案在左儿子和右儿子的交界处，即\(lson.rlen + rson.llen \ge x\)，则答案为左儿子包含右端点的最长的连续\(0\)的子串的左端点，即\(mid - lson.rlen + 1\)，直接返回即可
若答案在右儿子中，即\(rson.len\ge x\)，则遍历右儿子
代码如下

int query(int u, int l, int r, int x){
    if (l == r) return l;
    pushdown(u);
    int mid = l + r >> 1;
    if (tree[u << 1].len >= x) return query(u << 1, l, mid, x);
    else if (tree[u << 1].rlen + tree[u << 1 | 1].llen >= x) return mid - tree[u << 1].rlen + 1;
    else return query(u << 1 | 1, mid + 1, r, x);
}

主函数中需要注意的要点

执行操作\(1\)时，可以先判断根节点的\(len\)是否大于等于\(x\)，若不满足，说明区间中不存在这样的子串，直接输出0即可
否则可以证明此时一定有解，此时再去执行QUERY操作可以免去判断无解情况

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 50005;

struct Node{
    int sze, len, llen, rlen;
}tree[N * 4];
int lazytag[N * 4];
int n, m;

void pushup(int u){
    tree[u].sze = tree[u << 1].sze + tree[u << 1 | 1].sze;
    tree[u].len = max(tree[u << 1].len, tree[u << 1 | 1].len);
    tree[u].len = max(tree[u].len, tree[u << 1].rlen + tree[u << 1 | 1].llen);
    if (tree[u << 1].sze == tree[u << 1].llen) tree[u].llen = tree[u << 1].len + tree[u << 1 | 1].llen;
    else tree[u].llen = tree[u << 1].llen;
    if (tree[u << 1 | 1].sze == tree[u << 1 | 1].rlen) tree[u].rlen = tree[u << 1].rlen + tree[u << 1 | 1].len;
    else tree[u].rlen = tree[u << 1 | 1].rlen;
}

void pushdown(int u){
    if (!lazytag[u]) return ;
    if (lazytag[u] == 1) {
        tree[u << 1].len = tree[u << 1].rlen = tree[u << 1].llen = 0;
        tree[u << 1 | 1].len = tree[u << 1 | 1].rlen = tree[u << 1 | 1].llen = 0;
    }
    if (lazytag[u] == 2) {
        tree[u << 1].len = tree[u << 1].rlen = tree[u << 1].llen = tree[u << 1].sze;
        tree[u << 1 | 1].len = tree[u << 1 | 1].rlen = tree[u << 1 | 1].llen = tree[u << 1 | 1].sze;
    }
    lazytag[u << 1] = lazytag[u << 1 | 1] = lazytag[u];
    lazytag[u] = 0;
}

void build(int u, int l, int r){
    if (l == r){
        tree[u].len = tree[u].llen = tree[u].rlen = tree[u].sze = 1;
        return ;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void update(int u, int l, int r, int L, int R, int val){
    if (L <= l && r <= R){
        lazytag[u] = val;
        if (val == 1) tree[u].len = tree[u].rlen = tree[u].llen = 0;
        else if (val == 2) tree[u].len = tree[u].rlen = tree[u].llen = tree[u].sze;
        return ;
    }
    pushdown(u);
    int mid = l + r >> 1;
    if (L <= mid) update(u << 1, l, mid, L, R, val);
    if (R > mid) update(u << 1 | 1, mid + 1, r, L, R, val);
    pushup(u);
}

int query(int u, int l, int r, int x){
    if (l == r) return l;
    pushdown(u);
    int mid = l + r >> 1;
    if (tree[u << 1].len >= x) return query(u << 1, l, mid, x);
    else if (tree[u << 1].rlen + tree[u << 1 | 1].llen >= x) return mid - tree[u << 1].rlen + 1;
    else return query(u << 1 | 1, mid + 1, r, x);
}

int main(){
    scanf("%d%d", &n, &m);
    build(1, 1, n);
    while (m -- ){
        int op;
        scanf("%d", &op);
        if (op == 1){
            int x;
            scanf("%d", &x);
            if (tree[1].len < x) puts("0");
            else {
                int res = query(1, 1, n, x);
                printf("%d\n", res);
                if (res) update(1, 1, n, res, res + x - 1, 1);
            }
        }
        else {
            int a, b;
            scanf("%d%d", &a, &b);
            update(1, 1, n, a, a + b - 1, 2);
        }
    }
    return 0;
}

标签：子串,int,Hotel,tree,len,区间,USACO08FEB,lnsyoj336,llen
From： https://www.cnblogs.com/XiaoJuRuoUP/p/18221268/lnsyoj336_luoguP2894