营业额统计

形式化题目

给定 $n$ 天营业额 $a_1..a_n$ 。第 $i$ 天的波动值定义为 $\min_{j<i} |a_i - a_j|$ （第 1 天波动值为 $a_1$ 本身，按题面约定）。求每天波动值之和。

正解

思路

1. 在线动态「最近值」

逐日处理：每天需要在已出现的营业额集合里找与 $a_i$ 最接近的值，然后把 $a_i$ 插入集合。这是平衡树的模板操作：

插入：把 $a_i$ 放入 BST；
最近值查询：从根向下走，沿途维护「当前最优候选」，到空节点时返回最小距离。候选只可能是下降路径上每次「转向」时的分界值（前驱/后继）。

2. 数组式 Treap

用平铺数组 left/right/key/prio 实现 Treap（随机优先级小根堆维护平衡）：

迭代插入 + 显式 path 栈上浮旋转，避免递归（Python 递归深度与常数都不友好）；
旋转后按「祖父—父—子」的指针重接，逻辑清晰不易错。

期望树高 $O(\log n)$ ，总复杂度 $O(n\log n)$ 。Python 通过数组 + 迭代避免了链式对象与递归的双重常数，足以通过本题时限。

代码

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/**
 * 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-10 11:30
 * update_at: 2026-10-10 11:30
 */
// 营业额统计：treap 按营业额建 BST，逐天查最近的营业额。
#include <cstdio>
#include <vector>

typedef long long ll;

const ll INF = 1000000000000000000LL;

std::vector<ll> left_son; // 左儿子下标，0 表示空
std::vector<ll> right_son;
std::vector<ll> key;     // 该天营业额，同时是 BST 的键
std::vector<ll> prio;    // 随机优先级，小根堆保证期望树高 O(log n)
std::vector<ll> path;

ll rng_state = 20261010; // 固定种子：随机优先级可复现

ll rand30() {
    rng_state ^= rng_state << 13;
    rng_state ^= rng_state >> 7;
    rng_state ^= rng_state << 17;
    return rng_state & ((1LL << 30) - 1);
}

// 把 node 插入以 root 为根的 treap，返回插入后的新根
ll insert_node(ll root, ll node) {
    if (!root) return node;
    path.clear();
    ll cur = root;
    while (cur) {
        path.push_back(cur);
        cur = (key[node] < key[cur]) ? left_son[cur] : right_son[cur]; // 相等时往右挂
    }
    if (key[node] < key[path.back()]) {
        left_son[path.back()] = node;
    } else {
        right_son[path.back()] = node;
    }
    // 自底向上修正：node 的优先级比父节点小就旋转上浮
    while (!path.empty() && prio[node] < prio[path.back()]) {
        ll parent = path.back();
        path.pop_back();
        ll grand = path.empty() ? 0 : path.back();
        if (left_son[parent] == node) { // 右旋
            left_son[parent] = right_son[node];
            right_son[node] = parent;
        } else { // 左旋
            right_son[parent] = left_son[node];
            left_son[node] = parent;
        }
        if (grand) { // 换根后要接回祖父
            if (left_son[grand] == parent) left_son[grand] = node;
            else right_son[grand] = node;
        } else {
            root = node;
        }
    }
    return root;
}

// 在已插入的营业额里找与 value 距离最近的一个，返回该距离
ll nearest(ll root, ll value) {
    ll best = INF;
    ll cur = root;
    while (cur) {
        ll gap = value - key[cur];
        if (gap < 0) gap = -gap;
        if (gap < best) best = gap;
        if (value < key[cur]) cur = left_son[cur];
        else if (value > key[cur]) cur = right_son[cur];
        else return 0; // 出现过同一天营业额，波动值为 0
    }
    return best;
}

int main() {
    ll n;
    if (scanf("%lld", &n) != 1) return 0; // 空输入安全返回
    std::vector<ll> amount(n);
    for (ll i = 0; i < n; i++) {
        scanf("%lld", &amount[i]);
    }

    left_son.assign(n + 1, 0);
    right_son.assign(n + 1, 0);
    key.assign(n + 1, 0);
    prio.assign(n + 1, 0);
    for (ll i = 0; i < n; i++) {
        key[i + 1] = amount[i];
        prio[i + 1] = rand30();
    }

    ll ans = 0;
    ll root = 0; // 空树
    for (ll day = 0; day < n; day++) {
        ll value = amount[day];
        ll gap = (day == 0) ? value : nearest(root, value); // 第一天的最小波动值就是 a_1
        ans += gap;
        root = insert_node(root, day + 1); // 当天营业额进入集合
    }

    printf("%lld\n", ans);
    return 0;
}

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
82
83
84
85
86
87
88
89
90
91
92#!/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-10-02 10:20
# update_at: 2026-10-02 10:20

import sys
from random import getrandbits, seed

INF = 10 ** 18  # 查询日波动值时，"还没找到任何候选"的距离上界

# treap 用四个平铺数组表示，下标即天数（0 号位是空节点哨兵），靠下标运算代替链表。
left: list[int] = []   # 左儿子下标，0 表示空
right: list[int] = []  # 右儿子下标，0 表示空
key: list[int] = []    # 该天营业额，同时是 BST 的键
prio: list[int] = []   # 随机优先级，小根堆保证期望树高 O(log n)


def insert(root: int, node: int) -> int:
    """把 node 插入以 root 为根的 treap，返回插入后的新根。"""
    if not root:
        return node
    path: list[int] = []  # 下降路径，末位是 node 的父节点
    cur = root
    while cur:
        path.append(cur)
        cur = left[cur] if key[node] < key[cur] else right[cur]  # 相等时往右挂
    if key[node] < key[path[-1]]:
        left[path[-1]] = node
    else:
        right[path[-1]] = node
    # 自底向上修正：node 的优先级比父节点小就旋转上浮，直到堆性质恢复
    while path and prio[node] < prio[path[-1]]:
        parent = path.pop()
        grand = path[-1] if path else 0
        if left[parent] == node:  # 右旋：node 从左儿子升上来
            left[parent] = right[node]
            right[node] = parent
        else:  # 左旋
            right[parent] = left[node]
            left[node] = parent
        if grand:  # 换根后要接回祖父
            if left[grand] == parent:
                left[grand] = node
            else:
                right[grand] = node
        else:
            root = node
    return root


def nearest(root: int, value: int) -> int:
    """在已插入的营业额里找与 value 距离最近的一个，返回该距离。"""
    best = INF
    cur = root
    while cur:
        gap = abs(value - key[cur])
        if gap < best:
            best = gap
        if value < key[cur]:
            cur = left[cur]
        elif value > key[cur]:
            cur = right[cur]
        else:
            return 0  # 出现过同一天营业额，波动值为 0
    return best


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

    seed(1)  # 固定种子：随机优先级可复现，仍足以让树期望平衡
    left.extend([0] * (n + 1))
    right.extend([0] * (n + 1))
    key.extend([0] + amount)
    prio.extend([0] + [getrandbits(30) for _ in amount])

    ans = 0
    root = 0  # 空树
    for day, value in enumerate(amount):
        gap = value if day == 0 else nearest(root, value)  # 第一天的最小波动值就是 a_1
        ans += gap
        root = insert(root, day + 1)  # 当天营业额进入集合，供后面查询

    print(ans)


if __name__ == "__main__":
    solve()

复杂度

时间复杂度：期望 $O(n\log n)$ 。
空间复杂度： $O(n)$ 。

总结

「与历史某值差最小」= 平衡树维护动态集合 + 前驱/后继查询。
Python 写平衡树优先选数组式 + 迭代：省去对象开销与递归风险，常数显著更小。
Treap 随机优先级保证期望平衡，代码量比 Splay/AVL 小，是竞赛中的实用选择。

目录

形式化题目

正解

思路

1. 在线动态「最近值」

2. 数组式 Treap

代码

复杂度

总结