形式化题目

设身高是 $1 \sim n$ 的一个排列 $h_1, h_2, \ldots, h_n$。给定 $A_2, \ldots, A_n$（第 $1$ 头牛前面没有牛，$A_1 = 0$ 未列出），其中 $A_i$ 满足：

即第 $i$ 头牛前面比它矮的牛的数量。要求还原整个排列 $h$。

数据范围：$1 \leqslant n \leqslant 10^5$。

暴力解法

思路

核心观察来自最后一头牛：它前面站着全部 $n-1$ 头牛，所以 $A_n$ 就是全场比它矮的牛的数量，身高 $h_n = A_n + 1$ 直接被锁死，没有任何自由度。

把这个观察推广到从后往前的每一个位置。处理到位置 $i$ 时，位置 $i+1 \sim n$ 的牛 身高已经确定，可以认为这些身高被"占用"了。第 $i$ 头牛的身高应当是剩余空闲身高中 第 $A_i + 1$ 小的那个：

• 比 $h_i$ 小的身高共 $h_i - 1$ 个，其中恰有 $A_i$ 个要排在它前面；
• 剩下 $h_i - 1 - A_i$ 个更矮的身高留给后面的位置也没关系——后面的牛的约束 $A_j$ 只统计"它前面"的牛，往位置 $1 \sim i$ 里填什么更小的身高， 既不会冒出新的"比 $h_j$ 矮且在前面"的牛（那些身高已被 $A_i$ 的推导占位）， 也不会消失，归纳可证每一步的选择都合法且唯一。

于是得到朴素做法：逆序扫描，每次在剩余身高集合中"找第 $A_i+1$ 小并删除"。 用有序数组维护，每次找第 $k$ 小要 $O(n)$ 扫描，总复杂度 $O(n^2)$，$n = 10^5$ 时约 $10^{10}$ 次基本操作，不可行。

代码

复杂度与瓶颈

• 时间 $O(n^2)$：每头牛一次线性扫描找第 $k$ 小 + 一次 $O(n)$ 删除。
• 空间 $O(n)$。
• 瓶颈：动态集合上的"按名次查询"没有利用任何序结构，每次都从头数。

正解

关键观察

"在剩余身高集合中找第 $k$ 小并删除"是经典的可高效化结构：给每个身高一个 $0/1$ 标记（$1$ = 空闲），用树状数组维护前缀和，则

"第 $k$ 小的空闲身高"就是最小的 $x$ 使 $\text{pre}(x) \geqslant k$。 由于 $\text{pre}$ 对 $x$ 单调不减，可以在树状数组上倍增：从高位到低位贪心地 跳 $2^p$ 步，只要跳完后的前缀和仍 $< k$ 就跳过去并扣减 $k$， 一次下降同时完成定位，复杂度 $O(\log n)$。

思路

1. 初始化树状数组为全 $1$：tree[i] = i & -i 直接构造，前缀 $[1..i]$ 恰有 $i$ 个空闲。
2. 逆序枚举 $i = n \to 1$，在树状数组上倍增找第 $A_i + 1$ 小的空闲身高 $h_i$，记录答案。
3. 把身高 $h_i$ 的标记减 $1$（树状数组单点修改），表示该身高已占用。
4. 逆序求出的是 $h_n \ldots h_1$，最后反转输出。

用样例 $n = 5$，$A = [\_, 1, 2, 1, 0]$ 演示逆序推导：

表格从下往上读就是最终答案序列 $2, 4, 5, 3, 1$，与样例输出一致。 观察点：每一步"剩余空闲身高"恰好是"去掉比已确定身高更小的所有身高"后剩下的集合， 第 $A_i + 1$ 小自动保证了"前面有 $A_i$ 头更矮的牛"。

代码

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/**
 * 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
 */
// 排队：树状数组上倍增求「剩余身高中第 k 小」。
#include <cstdio>
#include <vector>

typedef long long ll;

const ll MAXN = 100005;

ll n;
ll a[MAXN];    // a[i]：第 i 头牛前面比它矮的数量（i ≥ 2）
ll tree[MAXN]; // 树状数组中 tree[i] 记录 (i-lowbit(i), i] 里空闲身高的个数
ll ans[MAXN];

// 树状数组上倍增：返回剩余（未被占用）身高中第 k 小的下标（1-based）
ll kth_free(ll k, ll log) {
    ll pos = 0;
    for (ll p = log; p >= 0; p--) {
        ll step = 1LL << p;
        ll nxt = pos + step;
        if (nxt <= n && tree[nxt] < k) { // 前缀和不够 k，第 k 小还在更右边
            pos = nxt;
            k -= tree[nxt];
        }
    }
    return pos + 1;
}

int main() {
    if (scanf("%lld", &n) != 1) return 0; // 空输入安全返回
    a[1] = 0; // 第 1 头牛前面没有牛
    for (ll i = 2; i <= n; i++) {
        scanf("%lld", &a[i]);
    }

    for (ll i = 1; i <= n; i++) {
        tree[i] = i & -i; // 初值即建树：所有身高都空闲
    }

    ll log = 1;
    while ((1LL << log) <= n) {
        log++;
    }
    log--; // 2^log ≤ n < 2^(log+1)

    for (ll i = n; i >= 1; i--) {
        // 从后往前确定：第 i 头牛的身高是剩余身高里第 a[i]+1 小的
        ll h = kth_free(a[i] + 1, log);
        ans[i] = h;
        ll p = h;
        while (p <= n) { // 身高 h 已被占用
            tree[p] -= 1;
            p += p & -p;
        }
    }

    for (ll i = 1; i <= n; i++) {
        printf("%lld\n", ans[i]);
    }
    return 0;
}

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#!/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-01 17:40
# update_at: 2026-10-01 17:40

import sys


def kth_free(tree: list[int], k: int, log: int) -> int:
    """树状数组上倍增：返回剩余（未被占用）身高中第 k 小的下标（1-based）。"""
    pos = 0
    for step in (1 << p for p in range(log, -1, -1)):
        nxt = pos + step
        if nxt < len(tree) and tree[nxt] < k:  # 前缀和不够 k，说明第 k 小还在更右边
            pos, k = nxt, k - tree[nxt]
    return pos + 1


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    a = [0, 0]  # a[0] 占位；a[1] = 0（第 1 头牛前面没有牛，未读入）
    for _ in range(n - 1):
        a.append(next(data))  # a[i]（i≥2）：第 i 头牛前面比它矮的数量

    tree = [0] * (n + 1)
    for i in range(1, n + 1):
        tree[i] = i & -i  # 初值即建树：所有身高都空闲，前缀 [1..i] 恰有 i 个空闲

    log = n.bit_length()  # 倍增跳的最大步长 2^log 覆盖 n
    ans: list[int] = []
    for i in range(n, 0, -1):
        # 从后往前确定：第 i 头牛的身高是剩余身高里第 a[i]+1 小的
        h = kth_free(tree, a[i] + 1, log)
        ans.append(h)
        p = h
        while p <= n:  # 树状数组单点 -1：身高 h 已被占用
            tree[p] -= 1
            p += p & -p

    print('\n'.join(map(str, reversed(ans))))


if __name__ == "__main__":
    solve()

实现说明：

• kth_free 是树状数组上倍增：步长从 $2^{\log n}$ 降到 $1$， tree[nxt] < k 说明第 $k$ 小还在更右边，跳过去并把 $k$ 扣掉这一段的前缀和； 结束时 pos + 1 就是第 $k$ 小的空闲身高。
• 输入只有 $n - 1$ 个数：a 数组长度为 $n + 1$，a[1] = 0（第 $1$ 头牛前面没有牛）， 这里的下标错位是最容易写错的坑。
• 逆序求出 ans 后 reversed 输出。

复杂度

• 时间 $O(n \log n)$：每头牛一次倍增定位（$\log n$ 步）+ 一次单点修改（$\log n$ 步）。
• 空间 $O(n)$。

总结

• 破题点是最后一头牛的身高被唯一确定，由此自然推出"从后往前 + 在剩余身高中取第 $A_i+1$ 小"。
• 朴素实现是 $O(n^2)$ 的线性扫描，瓶颈在动态第 $k$ 小查询； 树状数组 + 上倍增把它降到 $O(n \log n)$，且初始化可以用 i & -i 一步建好。
• 本题是"树状数组上倍增找第 $k$ 小"的标准入门模型：同样技巧适用于 权值第 $k$ 小、逆序对还原排列等一类问题。