【深基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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-10-07 09:37
 */
#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);
        // get_rank 的语义：x 存在时返回 x 的排名；x 不存在时返回第一个比 x 大的元素（后继）的排名。
        int rk = get_rank(root, x);
        bool exists = (rk <= tree[root].sz) && (kth(root, rk) == x);

        if (op == 1) {
            // 仓库里已经有这个长度就不再放
            if (exists) {
                puts("Already Exist");
            } else {
                insert(root, x);
            }
        } else {
            if (root == 0) {
                puts("Empty");
                continue;
            }

            int target;
            if (exists) {
                // 仓库里刚好有这个长度，直接取它
                target = x;
            } else {
                int prev_rank = rk - 1;  // 比 x 小的最大元素的排名；0 表示不存在
                int next_rank = rk;      // x 不存在时，get_rank 给出的就是后继的排名

                if (prev_rank < 1) {
                    target = kth(root, next_rank);
                } else if (next_rank > tree[root].sz) {
                    target = kth(root, prev_rank);
                } else {
                    int shorter = kth(root, prev_rank);
                    int longer = kth(root, next_rank);
                    // 两根木材距离相同时取较短的那根
                    target = (x - shorter <= longer - x) ? shorter : longer;
                }
            }
            printf("%d\n", target);
            erase(root, target);
        }
    }
    return 0;
}

STL 写法

用 set<ll> 保存仓库中现存的木材长度：set 自动去重并保持升序，正好对应“没有两根木材长度相同”以及“要按长度找最近的木材”。出货时用成员 lower_bound(len) 定位第一个不小于 len 的位置：它正好等于 len 就直接取它，否则把它和它的前一个位置（前驱）比较，距离更近者胜出，距离相同取较短的前驱。仓库为空输出 Empty，插入已有长度输出 Already Exist。对应的 cppbook 章节：set：自动去重并保持有序。

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/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 01:22
 * update_at: 2026-10-07 01:33
 */
// 这是 STL 写法：用 set<ll> 的成员 lower_bound 找第一个不小于需求长度的木材，
// 再把它和它的前一个位置比较，取出距离更近的一根（并列取较短的前驱）。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

set<ll> stock; // 仓库中现存的所有木材长度；set 自动去重并按长度升序保存

// 进货：仓库里已经有这个长度就报告 Already Exist，否则插入。
void add(ll len) {
    if (stock.count(len) > 0) {
        cout << "Already Exist" << '\n';
        return;
    }
    stock.insert(len);
}

// 出货：取出一根最接近需求长度 len 的木材，返回取出的长度。
// len 本身存在就取它；否则比较它的前驱和后继，距离相同取较短的前驱。
ll take(ll len) {
    auto it = stock.lower_bound(len); // 第一个不小于 len 的位置

    if (it != stock.end() && *it == len) { // 刚好有这个长度
        ll chosen = *it;
        stock.erase(it);
        return chosen;
    }

    // 此时 len 不在仓库里：it 指向后继（可能不存在），it 的前一个位置指向前驱（可能不存在）
    bool has_right = (it != stock.end());
    bool has_left = (it != stock.begin());

    if (!has_left) { // 没有比 len 短的木材，只能取后继
        ll chosen = *it;
        stock.erase(it);
        return chosen;
    }

    auto left_it = it;
    --left_it; // 前驱位置
    ll left_len = *left_it;

    if (!has_right) { // 没有比 len 长的木材，只能取前驱
        stock.erase(left_it);
        return left_len;
    }

    ll right_len = *it;
    // 距离相同时取较短的一根，也就是前驱
    if (len - left_len <= right_len - len) {
        stock.erase(left_it);
        return left_len;
    }
    stock.erase(it);
    return right_len;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll q;
    cin >> q;
    while (q--) {
        ll op, len;
        cin >> op >> len;
        if (op == 1) {
            add(len);
        } else {
            if (stock.empty()) {
                cout << "Empty" << '\n';
                continue;
            }
            cout << take(len) << '\n';
        }
    }

    return 0;
}

复杂度

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

总结

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