【深基17.例5】木材仓库

题意

维护一个长度互不相同的木材集合。支持插入；出货时删除等于需求长度的木材，否则删除距离需求最近的木材，距离相同选较短者。还要处理重复插入和空仓库。

思路

Python 标准库没有直接提供有序集合。普通有序列表配合 bisect 虽能找到位置，但中间插入、删除需要移动大量元素，最坏会达到 $O(q^2)$ 。

所有操作在开始时已经给出，可以先离线读完，把出现过的长度排序去重并映射到 1..k。树状数组的第 i 位表示该长度当前是否在仓库：

插入、删除是单点加 1 或 -1；
前缀和表示某个长度之前有多少根现存木材；
kth(rank) 找库存中第 rank 小的长度。

出货长度 x 不存在时，设严格小于 x 的库存数量为 left_count。第 left_count 小的是前驱，第 left_count+1 小的是后继。比较两边距离，使用 x-left <= right-x 保证距离相同时选较短的前驱。

Python 知识

集合推导式 {length for _, length in operations} 完成长度去重。
enumerate(lengths,1) 同时得到长度及其从 1 开始的树状数组下标。
set 负责期望 $O(1)$ 存在性判断，树状数组负责顺序和排名；两个容器各做自己擅长的事。
None 表示某一侧不存在候选，比设置超大哨兵更直观。
/home/rainboy/mycode/hugo-blog/content/program_language/python/sorting_and_ordering.md：排序、离散化与有序查询。
/home/rainboy/mycode/hugo-blog/content/program_language/python/collections_toolkit.md：集合的成员判断。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78import sys


class Fenwick:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def add(self, pos, delta):
        while pos <= self.n:
            self.tree[pos] += delta
            pos += pos & -pos

    def prefix_sum(self, pos):
        total = 0
        while pos:
            total += self.tree[pos]
            pos -= pos & -pos
        return total

    def kth(self, rank):
        pos = 0
        step = 1 << (self.n.bit_length() - 1)
        while step:
            nxt = pos + step
            if nxt <= self.n and self.tree[nxt] < rank:
                pos = nxt
                rank -= self.tree[nxt]
            step >>= 1
        return pos + 1


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    operations = list(zip(data[1::2], data[2::2]))
    lengths = sorted({length for _, length in operations})
    index = {length: i + 1 for i, length in enumerate(lengths)}

    bit = Fenwick(len(lengths))
    stock = set()
    answer = []

    for operation, length in operations:
        pos = index[length]
        if operation == 1:
            if length in stock:
                answer.append("Already Exist")
            else:
                stock.add(length)
                bit.add(pos, 1)
            continue

        if not stock:
            answer.append("Empty")
            continue

        if length in stock:
            chosen = length
        else:
            left_count = bit.prefix_sum(pos - 1)
            total = len(stock)
            left = lengths[bit.kth(left_count) - 1] if left_count else None
            right = lengths[bit.kth(left_count + 1) - 1] if left_count < total else None

            if right is None or left is not None and length - left <= right - length:
                chosen = left
            else:
                chosen = right

        answer.append(str(chosen))
        stock.remove(chosen)
        bit.add(index[chosen], -1)

    print("\n".join(answer))


if __name__ == "__main__":
    main()

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118/**
 * P5250 【深基17.例5】木材仓库
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int INF = 2147483647;

// BST 结点
struct Node {
    int val, l, r, cnt, sz;
} tree[MAXN];
int root, idx;

int new_node(int val) {
    ++idx;
    tree[idx].val = val;
    tree[idx].l = tree[idx].r = 0;
    tree[idx].cnt = tree[idx].sz = 1;
    return idx;
}

void insert(int &u, int val) {
    if (u == 0) { u = new_node(val); return; }
    ++tree[u].sz;
    if (val == tree[u].val) { ++tree[u].cnt; return; }
    if (val < tree[u].val) insert(tree[u].l, val);
    else insert(tree[u].r, val);
}

// 删除一个值（只删一个）
void erase(int &u, int val) {
    if (u == 0) return;
    if (val == tree[u].val) {
        if (tree[u].cnt > 1) { --tree[u].cnt; --tree[u].sz; return; }
        if (!tree[u].l || !tree[u].r) { u = tree[u].l + tree[u].r; return; }
        // 左右子树都存在：找前驱替换
        int v = tree[u].l;
        while (tree[v].r) v = tree[v].r;
        tree[u].val = tree[v].val;
        tree[u].cnt = tree[v].cnt;
        tree[v].cnt = 1;
        erase(tree[u].l, tree[v].val);
        tree[u].sz = tree[tree[u].l].sz + tree[tree[u].r].sz + tree[u].cnt;
        return;
    }
    if (val < tree[u].val) erase(tree[u].l, val);
    else erase(tree[u].r, val);
    tree[u].sz = tree[tree[u].l].sz + tree[tree[u].r].sz + tree[u].cnt;
}

// 查询 val 的排名
int get_rank(int u, int val) {
    if (u == 0) return 1;
    if (val == tree[u].val) return tree[tree[u].l].sz + 1;
    if (val < tree[u].val) return get_rank(tree[u].l, val);
    return tree[tree[u].l].sz + tree[u].cnt + get_rank(tree[u].r, val);
}

// 查询第 k 小
int kth(int u, int k) {
    if (u == 0) return 0;
    int lsz = tree[tree[u].l].sz;
    if (k <= lsz) return kth(tree[u].l, k);
    if (k <= lsz + tree[u].cnt) return tree[u].val;
    return kth(tree[u].r, k - lsz - tree[u].cnt);
}

// 前驱
int pre(int u, int val) {
    if (u == 0) return -INF;
    if (tree[u].val >= val) return pre(tree[u].l, val);
    return max(tree[u].val, pre(tree[u].r, val));
}

// 后继
int nxt(int u, int val) {
    if (u == 0) return INF;
    if (tree[u].val <= val) return nxt(tree[u].r, val);
    return min(tree[u].val, nxt(tree[u].l, val));
}

int main() {
    int q;
    scanf("%d", &q);
    while (q--) {
        int op, x;
        scanf("%d%d", &op, &x);
        if (op == 1) {
            // 仓库中是否已有
            int rk = get_rank(root, x);
            if (kth(root, rk) == x && root) puts("Already Exist");
            else insert(root, x);
        } else {
            if (root == 0) { puts("Empty"); continue; }
            int rk = get_rank(root, x);
            int smaller = kth(root, rk);
            int target;
            if (smaller == x) target = x;
            else {
                int big = kth(root, rk + 1);
                if (rk <= 1) target = big;
                else if (rk > tree[root].sz) target = smaller;
                else target = (x - smaller <= big - x) ? smaller : big;
            }
            printf("%d\n", target);
            erase(root, target);
        }
    }
    return 0;
}

复杂度

设操作数为 q。离散化需要 $O(q\log q)$ ，每次操作需要 $O(\log q)$ ，总时间复杂度 $O(q\log q)$ ，空间复杂度 $O(q)$ 。

总结

需要动态前驱、后继时，不能只看到 bisect 查询快，还要计算列表修改成本。离线坐标压缩把大整数长度变成排名，再用树状数组维护哪些排名仍存在。

【深基17.例5】木材仓库

目录

题意

思路

Python 知识

代码

复杂度

总结