「一本通 4.6 练习 1」宠物收养所

GitHub跳转原题关系图返回列表

使用离散化结合树状数组倍增（或平衡树）动态维护待匹配集合的前驱与后继

OJ: roj

题目 ID: 1566

难度:提高

标签:树状数组平衡树离散化

创建: 2026-09-30 18:36

更新: 2026-10-07 13:50

形式化题目

维护一个动态多重集 $S$ 和当前集合所归属的实体类型 $T \in \{0, 1\}$ 。初始时 $S = \varnothing$ 。给定 $n$ 个按时间先后到达的二元组操作 $(kind, b)$ ：

若 $S = \varnothing$ ，则令 $T \leftarrow kind$ ，并将 $b$ 插入 $S$ ；
若 $S \neq \varnothing$ 且 $kind = T$ ，则直接将 $b$ 插入 $S$ ；
若 $S \neq \varnothing$ 且 $kind \neq T$ ，则在 $S$ 中查询与 $b$ 差值绝对值最小的元素 $x$ ：
- 若存在两个元素与 $b$ 的绝对差相同（即 $b - d$ 与 $b + d$ 均存在），优先选择较小的元素 $b - d$ ；
- 产生不满意度代价 $|x - b|$ ；
- 将选中的元素 $x$ 从 $S$ 中删除；若删除后 $S = \varnothing$ ，则 $T$ 重置为未指定状态。

求所有匹配产生的不满意度总和对 $10^6$ 取模后的值。

graph TD
    A[新事件 kind, b 到达] --> B{池为空 或 kind == 池类型?}
    B -- 是 --> C[将 b 插入集合 S, 维护池类型]
    B -- 否 --> D[在集合 S 中查找 b 的前驱 left 和后继 right]
    D --> E[按距离最小且相同时取较小者选定最佳匹配 x]
    E --> F[累加代价 |x - b| % 10^6]
    F --> G[从 S 中删除 x]

正解

思路

1. 朴素做法及其瓶颈

最直接的思路是用一个数组或列表保存收养所中现存的对象：

当到来同类对象或池为空时，直接追加到列表末尾，耗时 $O(1)$ ；
当到来异类对象需要匹配时，遍历列表中的每一个已有元素，找出与 $b$ 之差绝对值最小的元素，并在并列时取较小者，耗时 $O(|S|)$ ；然后将该元素从列表中删除。

在最坏情况下，收养所内堆积的元素数量可达 $O(n)$ 级别，总时间复杂度为 $O(n^2)$ 。面对 $n = 8 \times 10^4$ ，最坏操作次数达到约 $6.4 \times 10^9$ ，必然大幅超时。瓶颈在于无序列表无法在对数时间内完成前驱、后继查找与动态删除。

2. 优化：动态前驱与后继查询

在一个单调有序的集合中，与给定值 $b$ 差值绝对值最小的元素，必然只可能出现在以下两个候选者中：

前驱 $left$ ：集合中 $\leqslant b$ 的最大元素；
后继 $right$ ：集合中 $\geqslant b$ 的最小元素。

选定前驱与后继后，只需根据题面规则做一次常数级别的比较：

若 $left$ 和 $right$ 均存在，当 $b - left \leqslant right - b$ 时，选择 $left$ ；否则选择 $right$ ；
若仅有一个存在，则直接选择存在的那个。

选出最佳元素后将其移出集合，并累加 $|x - b|$ 。

在 C++ 中，该过程可以直接使用 std::set 并在 $O(\log n)$ 内通过 lower_bound 找到后继以及通过迭代器前移找到前驱。在 Python 标准库中没有现成的平衡二叉搜索树。由于全部 $n$ 次操作的输入是完全已知的（离线问题），我们可以先将所有操作中出现的数值 $b$ 收集、去重并排序，进行离散化映射到 $[1, m]$ 。

在离散化后的值域上建立树状数组（Fenwick Tree），记录每个离散化位置是否存在当前可用元素：

插入/删除：对应离散化位置单点 $+1$ 或 $-1$ ，耗时 $O(\log m)$ ；
统计小于 $b$ 的元素个数：对离散化位置 $pos - 1$ 查询前缀和，得到 $left\_cnt$ ，耗时 $O(\log m)$ ；
定位前驱与后继：
- 前驱是集合中第 $left\_cnt$ 小的元素（当 $left\_cnt > 0$ 时）；
- 后继是集合中第 $left\_cnt + 1$ 小的元素（当 $left\_cnt < |S|$ 时）；
- 树状数组可以通过二进制倍增在 $O(\log m)$ 时间内求出第 $k$ 小元素的离散化位置。

由此，每次操作均能在 $O(\log n)$ 时间内完成。

代码

Python 版：

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
78
79
80
81#!/usr/bin/env python3
# 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-09-30 18:36
# update_at: 2026-09-30 18:36

import sys

MOD = 1_000_000


def query_kth(tree: list[int], k: int, limit: int) -> int:
    """在树状数组上倍增查找第 k 小元素对应的值域离散化下标。"""
    pos, step = 0, 1 << (limit.bit_length() - 1)
    while step:
        nxt = pos + step
        if nxt <= limit and tree[nxt] < k:
            pos = nxt
            k -= tree[nxt]
        step >>= 1
    return pos + 1


def pick_best(b: int, left: int | None, right: int | None) -> int:
    """在前驱和后继中选取最接近的值，差值相等时优先选择前驱。"""
    if left is None:
        return right  # type: ignore[return-value]
    if right is None:
        return left
    return left if b - left <= right - b else right


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    events = [(next(data), next(data)) for _ in range(n)]

    coords = sorted({b for _, b in events})
    idx = {v: i + 1 for i, v in enumerate(coords)}
    m = len(coords)
    tree = [0] * (m + 1)

    def add(p: int, v: int) -> None:
        while p <= m:
            tree[p] += v
            p += p & -p

    def prefix_sum(p: int) -> int:
        total = 0
        while p:
            total += tree[p]
            p -= p & -p
        return total

    ans = 0
    pool_type: int | None = None
    pool_size = 0

    for kind, b in events:
        if pool_size == 0 or pool_type == kind:
            pool_type = kind
            add(idx[b], 1)
            pool_size += 1
            continue

        pos = idx[b]
        left_cnt = prefix_sum(pos - 1)
        left = coords[query_kth(tree, left_cnt, m) - 1] if left_cnt else None
        right = coords[query_kth(tree, left_cnt + 1, m) - 1] if left_cnt < pool_size else None

        chosen = pick_best(b, left, right)
        ans = (ans + abs(b - chosen)) % MOD
        add(idx[chosen], -1)
        pool_size -= 1

    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-05 08:49
 * update_at: 2026-10-05 08:49
 */
#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;

typedef long long ll;

const int MAXN = 80005;
const ll MOD = 1000000;

ll n;
ll kind[MAXN];  // 第 i 个事件：0 表示宠物，1 表示领养者
ll value[MAXN]; // 第 i 个事件的特点值
ll idx[MAXN];   // value[i] 离散化后的下标（从 1 开始）

ll coord[MAXN]; // 所有出现过的特点值去重排序，下标从 1 开始
ll coord_cnt;

ll tree[MAXN]; // 树状数组，tree 维护每个离散化位置上待匹配对象的个数

int pool_type;  // 待匹配池当前的归属类型：0 宠物 / 1 领养者
ll pool_size;   // 待匹配池中的对象个数
ll answer;      // 所有匹配产生的不满意度总和（对 10^6 取模）

// 单点修改：离散化下标 p 的计数加上 delta。
void add(ll p, ll delta) {
    for (; p <= coord_cnt; p += p & -p) {
        tree[p] += delta;
    }
}

// 查询离散化下标 1..p 的前缀计数和。
ll prefix_sum(ll p) {
    ll sum = 0;
    for (; p > 0; p -= p & -p) {
        sum += tree[p];
    }
    return sum;
}

// 在树状数组上二进制倍增，求出第 k 小元素所在的离散化下标。
ll kth(ll k) {
    ll pos = 0;
    ll step = 1;
    while (step * 2 <= coord_cnt) {
        step *= 2;
    }
    for (; step > 0; step /= 2) {
        ll nxt = pos + step;
        if (nxt <= coord_cnt && tree[nxt] < k) {
            pos = nxt;
            k -= tree[nxt];
        }
    }
    return pos + 1;
}

void read_input() {
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> kind[i] >> value[i];
    }
}

// 把全部特点值收集、去重、排序，得到离散化下标。
void build_discretization() {
    for (ll i = 1; i <= n; i++) {
        coord[i] = value[i];
    }
    sort(coord + 1, coord + n + 1);
    coord_cnt = unique(coord + 1, coord + n + 1) - (coord + 1);
    for (ll i = 1; i <= n; i++) {
        idx[i] = lower_bound(coord + 1, coord + coord_cnt + 1, value[i]) - coord;
    }
}

void solve() {
    for (ll i = 1; i <= n; i++) {
        // 池为空或到来者与池中对象同类：直接入池。
        if (pool_size == 0 || pool_type == kind[i]) {
            pool_type = kind[i];
            add(idx[i], 1);
            pool_size++;
            continue;
        }

        // 异类到来：在池中找前驱（<=value 的最大值）与后继（>=value 的最小值）。
        ll left_cnt = prefix_sum(idx[i] - 1);
        ll best_pos;
        if (left_cnt == 0) {
            best_pos = kth(left_cnt + 1); // 没有前驱，只能取后继
        } else if (left_cnt == pool_size) {
            best_pos = kth(left_cnt); // 没有后继，只能取前驱
        } else {
            ll left_pos = kth(left_cnt);
            ll right_pos = kth(left_cnt + 1);
            // 差值相等时题面要求取较小的那个，即前驱。
            if (value[i] - coord[left_pos] <= coord[right_pos] - value[i]) {
                best_pos = left_pos;
            } else {
                best_pos = right_pos;
            }
        }

        answer = (answer + abs(value[i] - coord[best_pos])) % MOD;
        add(best_pos, -1);
        pool_size--;
    }
    cout << answer << "\n";
}

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

    read_input();
    build_discretization();
    solve();

    return 0;
}

复杂度

时间复杂度：
- 提取所有操作数值去重排序离散化： $O(n \log n)$ ；
- 每个事件进行树状数组的前缀和查询、单点修改与倍增查找第 $k$ 小，单次耗时 $O(\log n)$ ；
- 处理全部 $n$ 个事件总时间复杂度为 $O(n \log n)$ 。在 $n = 8 \times 10^4$ 规模下，Python 耗时约 0.15 秒，运行效率极高。
空间复杂度：存储离散化数组、位置映射表及树状数组的空间消耗均为 $O(n)$ 。

总结

本题的核心特征是宠物的领养与领养者的等待在数学上是对称的，二者共享同一个「等待池」的动态维护逻辑。通过将动态维护有序集合的问题转化为离线离散化与树状数组前缀和，利用倍增在树状数组上实现快速前驱与后继定位，既保证了与平衡树同阶的 $O(n \log n)$ 渐进复杂度，又避免了手写复杂平衡树（如 Treap / Splay）的常数与代码量开销。

【题目描述】

原题来自：HNOI 2004

最近，阿 Q 开了一间宠物收养所。收养所提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。每个领养者都希望领养到自己满意的宠物，阿 Q 根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值 $a$ （ $a$ 是一个正整数， $a<2^{31}$ ），而他也给每个处在收养所的宠物一个特点值，这样他就能够很方便的处理整个领养宠物的过程了。

宠物收养所总是会有两种情况发生：被遗弃的宠物过多或者是想要收养宠物的人太多，而宠物太少：

被遗弃的宠物过多时，假若到来一个领养者，这个领养者希望领养的宠物的特点值为 $a$ ，那么它将会领养一只目前未被领养的宠物中特点值最接近 $a$ 的一只宠物。任何两只宠物的特点值都不可能是相同的，任何两个领养者的希望领养宠物的特点值也不可能是一样的。如果有两只满足要求的宠物，即存在两只宠物他们的特点值分别为 $a-b$ 和 $a+b$ ，那么领养者将会领养特点值为 $a-b$ 的那只宠物；

收养宠物的人过多，假若到来一只被收养的宠物，那么哪个领养者能够领养它呢？能够领养它的领养者，是那个希望被领养宠物的特点值最接近该宠物特点值的领养者，如果该宠物的特点值为 $a$ ，存在两个领养者他们希望领养宠物的特点值分别为 $a-b$ 和 $a+b$ ，那么特点值为 $a-b$ 的那个领养者将成功领养该宠物。一个领养者领养了一个特点值为 $a$ 的宠物，而它本身希望领养的宠物的特点值为 $b$ ，那么这个领养者的不满意程度为 $|a-b|$ 。

你得到了一年当中，领养者和被收养宠物到来收养所的情况，希望你计算所有收养了宠物的领养者的不满意程度的总和。这一年初始时，收养所里面既没有宠物，也没有领养者。

【输入】

第一行为一个正整数 $n$ ，表示一年当中来到收养所的宠物和领养者的总数；

接下来的 $n$ 行，按到来时间的先后顺序描述了一年当中来到收养所的宠物和领养者的情况。每行有两个正整数 $a, b$ ，其中 $a=0$ 表示宠物， $a=1$ 表示领养者， $b$ 表示宠物的特点值或是领养者希望领养宠物的特点值。

同一时间呆在收养所中的，要么全是宠物，要么全是领养者，这些宠物和领养者的个数不会超过 $10^4$ 个。

【输出】

仅有一个正整数，表示一年当中所有收养了宠物的领养者的不满意程度的总和对 $10^6$ 取模以后的结果。

【输入样例】

text

【输出样例】

text

【提示】

样例说明：

$|3-2|+|2-4|=3$ ，最后一个领养者没有宠物可以领养。

数据范围与提示：

对于全部数据， $1≤n≤8×10^4$ 。

【来源】

一本通在线评测