AcWing 261. 旅馆【线段树】

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 261. 旅馆【线段树】原题链接简单

作者：

滑稽_ωﾉ , 2020-05-15 17:30:14 , 所有人可见 , 阅读 2230

23

4

题目描述

维护一个长度为 $n$ 的01串，初始全部为0，进行 $m$ 次操作

找到最靠左的长度为 $len$ 的全部为0的子串，输出左端点并把这个子串全部赋值为1，如果不存在就输出0
把左端点为 $l$ 长度为 $len$ 的子串全部赋值为0

$n, m \leq 5 · 10 ^ 4$

懒标记线段树

和这道题 AcWing.245 你能回答这些问题吗类似

维护区间内最长的 $0$ 串长度 $d$ 需要同时维护以左端点开始的最长 $0$ 串长度 $ld$ ，和以右端点结束的最长的 $0$ 串长度 $rd$
用子节点更新父节点时可能会有左子节点右边的一截和右子节点左边的一截拼起来的情况

root.d = max(left.d, right.d, left.rd + right.ld)

询问时由于要找最靠左的满足条件的，那就从左往右依次询问
如果左子节点有满足条件的 $0$ 串，那就返回左子节点的询问
如果左子节点和右子节点能拼出满足条件的 $0$ 串，那就返回拼出的这个串的左端点
如果右子节点有满足条件的 $0$ 串，那就返回右子节点的询问
否则返回 0

再有就是普通的懒标记下传，记得递归之前~~没事干~~都要pushdown一下。

时间复杂度 $O(mlogn)$

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 50010;

struct Node {
    int l, r;
    int d, ld, rd;
    int lazy;
}tr[N << 2];

void build(int u, int l, int r) {
    int len = r - l + 1;
    tr[u] = {l, r, len, len, len, -1};
    if (l == r) return;
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

void solve(Node &u, int lazy) {
    if (lazy == 1) u.d = u.ld = u.rd = 0;
    if (lazy == 0) u.d = u.ld = u.rd = u.r - u.l + 1;
    u.lazy = lazy;
}

void pushdown(Node &u, Node &left, Node &right) {
    if (u.lazy != -1) {
        solve(left, u.lazy);
        solve(right, u.lazy);
        u.lazy = -1;
    }
}

void pushdown(int u) {
    pushdown(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

int query(int u, int len) {
    if (tr[u].l == tr[u].r) {
        if (tr[u].d) return tr[u].l;
        return 0;
    }

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (tr[u << 1].d >= len) return query(u << 1, len);
    if (tr[u << 1].rd + tr[u << 1 | 1].ld >= len) return tr[u << 1].r - tr[u << 1].rd + 1;
    if (tr[u << 1 | 1].d >= len) return query(u << 1 | 1, len);
    return 0;
}

void pushup(Node &u, Node &left, Node &right) {
    u.ld = left.ld;
    if (left.d == left.r - left.l + 1) u.ld = left.d + right.ld;
    u.rd = right.rd;
    if (right.d == right.r - right.l + 1) u.rd = right.d + left.rd;
    u.d = max(max(left.d, right.d), left.rd + right.ld);
}

void pushup(int u) {
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void modify(int u, int l, int r, int lazy) {
    if (tr[u].l >= l && tr[u].r <= r) {
        solve(tr[u], lazy);
        return;
    }

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) modify(u << 1, l, r, lazy);
    if (r > mid) modify(u << 1 | 1, l, r, lazy);
    pushup(u);
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    build(1, 1, n);
    while (m --) {
        int op, x, len;
        scanf("%d", &op);
        if (op == 1) {
            scanf("%d", &len);
            x = query(1, len);
            printf("%d\n", x);
            if (x) modify(1, x, x + len - 1, 1);
        } else {
            scanf("%d%d", &x, &len);
            modify(1, x, x + len - 1, 0);
        }
    }
    return 0;
}

15 评论

shuhehehehe 3个月前

HACKED!!!!!!

滑稽_ωﾉ 3个月前

更新了代码

hxzz 6个月前

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 5e5 + 5;

struct Node {
    int l, r;
    int empty, lempty, rempty; // 从区间左端点开始的空房间，从区间右边端点开始的空房间, empty 为最大的空房间
    int lazy; // 1 表示子节点需要退租，2 子节点需要入住， 0 表示没有懒标记
}tr[N * 4];


void pushup(Node &u, Node &left, Node &right) {
    u.lempty = left.lempty;
    if (left.empty == left.r - left.l + 1) 
        u.lempty += right.lempty;
    u.rempty = right.rempty;
    if (right.empty == right.r - right.l + 1)
        u.rempty += left.rempty;
    u.empty = max(max(left.empty, right.empty), left.rempty + right.lempty);
}

void pushup(int u) {
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void eval(Node &t, int lazy) {
    if (lazy == 1) {
        int len = t.r - t.l + 1;
        t.lempty = t.rempty = t.empty = len;
    }
    if (lazy == 2) {
        t.lempty = t.rempty = t.empty = 0;
    }
}

void pushdown(int u) {
    if (tr[u].lazy == 0)
        return ;
    int lazy = tr[u].lazy;
    eval(tr[u << 1], lazy);
    eval(tr[u << 1 | 1], lazy);
    tr[u << 1].lazy = lazy;
    tr[u << 1 | 1].lazy = lazy;
    tr[u].lazy = 0;
}

void build(int u, int l, int r) {
    if (l == r) {
        tr[u] = { l, r, 1, 1, 1, 0 };
        return;
    } else {
        tr[u] = { l, r, 0, 0, 0, 0 };
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int lazy) {
    if (tr[u].l >= l && tr[u].r <= r) {
        eval(tr[u], lazy);
        tr[u].lazy = lazy;
    } else {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, lazy);
        if (r > mid) modify(u << 1 | 1, l, r, lazy);
        pushup(u);
    }
}


int query_left_point(int u, int len) {
    if (tr[u].empty < len)
        return 0;
    if (tr[u].lempty >= len)
        return tr[u].l;
    pushdown(u);
    if (tr[u << 1].empty >= len) return query_left_point(u << 1, len);
    if (tr[u << 1].rempty + tr[u << 1 | 1].lempty >= len) 
        return tr[u << 1].r - tr[u << 1].rempty + 1;
    if (tr[u << 1 | 1].empty >= len) return query_left_point(u << 1 | 1, len);

    return 0;
}

int main() {
    int n, m;
    cin >> n >> m;
    build(1, 1, n);
    while (m --) {
        int op;
        cin >> op;
        if (op == 1) {
            int len;
            cin >> len;
            int left_point = query_left_point(1, len);
            cout << left_point << endl;
            if (left_point)
                modify(1, left_point, left_point + len - 1, 2);
        } else {
            int left, len;
            cin >> left >> len;
            modify(1, left, left + len - 1, 1);
        }
    }
    return 0;
}

hxzz 6个月前

query 需要加上 if (tr[u].ld >= len)
return tr[u].l;

liyiHuan 2023-02-20 20:51

%%%

南岸以南南岸哀 2022-08-09 00:43

if(tr[u<<1].ld==len) return tr[u]. l;
if(tr[u << 1].d >= len) return query(u << 1, len);
if(tr[u << 1].rd + tr[u << 1 | 1].ld == len) return tr[u << 1].r - tr[u << 1].rd + 1;
if(tr[u << 1].rd + tr[u << 1 | 1].ld >= len) return tr[u << 1].r - tr[u << 1].rd + 1;
if(tr[u << 1 | 1].ld == len) return tr[u].l;
if(tr[u << 1 | 1].d >= len) return query(u << 1 | 1, len);