ALGORITHM NOTES阅读地图
8个主要章节
1段代码示例
6组图片与图表

先明确状态与不变量，再对照手算、证明、边界和实现。

章节速览8 节 · 展开选择

在树状数组序列计数里，树状数组经常保存“某个值出现了几次”。这次要把每个仍可使用的值 v 存成权重 v，再反过来追问：前缀和第一次超过一个给定数的位置在哪里？

这篇沿着逆序处理的思路继续走。倒着恢复并非为了反转循环本身，而是为了让“左侧还有哪些数”变成一个已经确定的集合。

官方题意与为什么正序难猜

1208D · Restore Permutation 官方难度 1900，标签为 binary search、data structures、greedy、implementation。元信息与约束核对于 2026-10-22；亦可查阅官方题目 API。

原排列 p 恰好包含 1 到 n 各一次。输入给出每个位置 i 的 sᵢ：在 i 之前、数值又小于 pᵢ 的那些元素的数值之和。例如左侧较小的值是 1 和 3，贡献为 4，而非元素个数 2。

范围为 1≤n≤200000、0≤sᵢ≤n(n−1)/2，保证输入来自合法排列，答案唯一。正文重新组织解法，不复述整段题面。

正序处理时，sᵢ=0 并不能确定 pᵢ：它可能是当前出现过的最小值，也可能左侧根本没有元素。若枚举所有排列，搜索规模达到 n!；即使已经想到逆序，每次线性扫描剩余值仍需 O(n²)。

逆序以后，剩余集合就是原前缀

从 i=n 向 1 恢复，令 U 为尚未被放入答案的数值集合。处理位置 i 前，不变量是：

U 恰好由真实排列的 p₁,…,pᵢ 组成，已经恢复的后缀不再属于 U。

初始 U={1,…,n}，显然成立。现在假设真实 pᵢ=x。U 中除 x 外的所有值都在原位置 i 左侧，因此

sᵢ = U 中所有严格小于 x 的值之和。

原题同时要求“在左侧”和“值更小”，逆序后，前一项已经由 U 的定义自动满足，只需在数值轴上找后一项。

找到首个超过 s 的加权前缀

定义值域权重 w[v]：v∈U 时为 v，否则为 0；再定义 F(t)=w[1]+…+w[t]，并令 F(0)=0。

对于刚才的 x，恰有 F(x−1)=sᵢ，而 F(x)=sᵢ+x>sᵢ。对任何 t<x 都有 F(t)≤sᵢ。因此 x 正是：

最小的、使 F(x)>sᵢ 成立的数值位置。

删除过的位置权重为零，会产生平坦段，但不会改变这个“首次严格超过”的定义。合法输入保证该位置存在，且它的当前权重大于零。计数第 k 小与本题不是同一个权重模型；不能把 sᵢ 直接当作还剩多少个较小元素。

排列3、1、5、2、4对应输入0、0、4、1、6。恢复第四项前已删去值4；剩余权重1、2、3、0、5，前缀1、3、6、6、11，首次超过1的位置为值2。
原创教学图，采用下文自拟排列。数值轴保留已删除的槽位；删除值 4 以后 F(3)=F(4)=6，平坦段仍可参与前缀边界搜索。查看原图

这也给出完整正确性证明：归纳假设成立时，上述边界唯一选出真实 pᵢ。将它从 U 移除后，U 恰好剩下 p₁,…,pᵢ₋₁，不变量继续成立。到 i=1 时恢复全部排列。每步都是唯一选择，因此合法 s 不可能对应两个不同排列。

树状数组倍增为何只需一层对数

树状数组保存权重和，删除值 x 就执行 add(x,-x)。初始化时对每个 v 加入 v；不需要把原数组下标 i 存进树状数组。

若对值域二分，每次调用一次前缀求和，单次选择会是 O(log²n)。树状数组自己的块结构允许直接倍增，把选择降为 O(log n)。维护 pos 与 acc：acc 始终等于 F(pos)，且不超过目标 s。

从不大于 n 的最大二次幂 step 开始，尝试 next=pos+step。在这个倍增顺序下，pos 是 2×step 的倍数，因此 next 的 lowbit 恰为 step，tree[next] 正好覆盖 (pos,next]。于是 acc+tree[next] 就是 F(next)，不必重新查询。

如果 next≤n 且候选和≤s，就接受整块，更新 pos 和 acc；否则保留原位置。随后 step 减半。在每个二进制位选择最大可行前缀，最终得到最大的 F(pos)≤s 的位置，答案为 pos+1。

所有权重非负，故 F 单调不减，这是倍增选择的前提。搜索采用 ≤s 的可跳过前缀，才能返回首个 >s 的位置；若把等号写反，就会在恰好命中的边界提前停止。

初始权重为1到5且目标为6。步长4候选前缀10拒绝，步长2候选前缀3接受，步长1候选前缀6接受，最终位置3加1得到值4。
原创倍增演算，展示恢复最后一项时的真实整数步骤。F(3)=6 恰好等于 s₅，仍须跳过；首次超过 6 的是 F(4)=10。图不是性能测量。查看原图

五个数的完整手算

自拟排列 p=[3,1,5,2,4]。逐位置按定义编码，得到 s=[0,0,4,1,6]：第三项前面较小的是 3 与 1，第五项前面较小的是 3、1、2。

恢复位置 i选择前剩余集合 Usᵢ首个跨越边界恢复 pᵢ删除的权重
5{1,2,3,4,5}6F(3)=6，F(4)=1044
4{1,2,3,5}1F(1)=1，F(2)=322
3{1,3,5}4F(4)=4，F(5)=955
2{1,3}0F(0)=0，F(1)=111
1{3}0F(2)=0，F(3)=333

答案写回原下标，因此输出仍为 3 1 5 2 4，不把恢复顺序 4 2 5 1 3 直接打印出来。第三行的 F(4)=4 包含已经删除的值 2、4 的零权槽位；搜索的是数值位置，而非集合中元素的连续编号。

自检：sᵢ=0 时应该固定选择值 1 吗？

应该选当前剩余集合的最小值。例子最后只剩 {3}，F(1)=F(2)=0，首个超过零的位置是 3；值 1 早已用于第二项。

自检：恢复第五项时，前缀和恰好达到 6，为何还要继续？

s₅只计算严格小于 p₅ 的剩余值。和值为 6 的前缀仍位于答案之前，应跳过；再加入答案本身的正权重才会首次超过 6。本例因此得到 4，而非 3。

完整 C++17 实现

实现遵守题目保证，不另行定义非法输入的输出协议。firstPrefixGreater 的调用前提是权重非负且 0≤target<全部剩余权重和；合法重建每一步都满足它。

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
#include <iostream>
#include <vector>

class Fenwick {
public:
    explicit Fenwick(int size) : n(size), tree(size + 1, 0) {}

    void add(int pos, long long delta) {
        for (; pos <= n; pos += pos & -pos) {
            tree[pos] += delta;
        }
    }

    int firstPrefixGreater(long long target) const {
        int pos = 0;
        long long acc = 0;
        int step = 1;
        while (step <= n / 2) step <<= 1;
        for (; step > 0; step >>= 1) {
            const int next = pos + step;
            if (next <= n && acc + tree[next] <= target) {
                pos = next;
                acc += tree[next];
            }
        }
        return pos + 1;
    }

private:
    int n;
    std::vector<long long> tree;
};

std::vector<int> restorePermutation(const std::vector<long long>& s) {
    const int n = static_cast<int>(s.size());
    Fenwick sums(n);
    for (int value = 1; value <= n; ++value) sums.add(value, value);
    std::vector<int> answer(n);
    for (int i = n - 1; i >= 0; --i) {
        const int value = sums.firstPrefixGreater(s[i]);
        answer[i] = value;
        sums.add(value, -static_cast<long long>(value));
    }
    return answer;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n = 0;
    if (!(std::cin >> n)) return 0;
    std::vector<long long> s(n);
    for (long long& value : s) std::cin >> value;
    const std::vector<int> answer = restorePermutation(s);
    for (int i = 0; i < n; ++i) {
        if (i != 0) std::cout << ' ';
        std::cout << answer[i];
    }
    std::cout << '\n';
    return 0;
}

边界与复杂度

初始化 n 次加入；每个位置进行一次 O(log n) 选择与一次 O(log n) 删除。因此总时间 O(n log n)，空间 O(n)。也可以线性初始化树状数组，但不改变整个重建的渐进时间。

情况 应有行为 常见错误
n=1、s=[0] 返回 [1] 起始倍增步长错误
全部 sᵢ=0 每轮取当前最小值，最终原排列递减 总是选择值 1，或输出恢复顺序
原排列递增 sᵢ=i(i−1)/2 将数值和误作元素个数
前缀恰好等于 sᵢ 继续跳过，寻找首个严格大于 倍增判断误写为严格小于
删除产生零权平坦段 可以连续跳过，答案仍为非零权位置 误以为前缀必须严格递增
n 不是二次幂 对每个候选检查 next≤n 只按整棵完全树处理
最大规模 所有权重和与输入使用 long long int 前缀溢出，或删除时只减 1

最大 n=200000 时，输入上界为 19999900000，初始全部权重和为 20000100000，均超过有符号 32 位整数。树节点、输入与累积量都使用 long long；下标与单个排列值使用 int 足够。

如果输入不保证合法，只有 0≤sᵢ<剩余总和 还不足以验证：还必须检查选中值之前的精确加权前缀等于 sᵢ。例如剩余值 {1,3} 时，目标 2 落在一次跳跃内部，虽能找到首个超过它的位置 3，却不存在恰好为 2 的较小值之和。本实现依赖官方合法性保证，不把“有上界位置”误当作完整合法性检查。

验证与继续阅读

验证程序 tests/verify-restore-permutation-article.cjs 从正文提取原样 C++17，以 -O2 -Wall -Wextra -pedantic -Werror 在 MinGW g++ 13.1.0 无警告编译。n=1…8 的全部 46233 个排列按原定义逐对编码，既核对恢复值，也核对这些编码互不相同；另有 600 个预定种子的随机排列与上文手算，合计 46834 个批量实例。

原样 main 另运行 6 例，包含递增、递减、高低交替的三组 n=200000 边界；大规模参考采用归并排序累计贡献，不复用树状数组选择。全部检查共恢复 1030743 个值，另核对 74168 个任意非负权前缀选择，覆盖零权平坦段与恰好命中的边界。五行手算和两图结构也经程序检查，54 个图中文字节点均在画布内；验证针对合法整数模型，不把本机耗时当作所有评测机的保证。

先回到树状数组计数与逆序奇偶，比较“查询给定前缀的和”与“根据和选择前缀边界”；再看单调栈重建山峰，比较哪些重建问题靠剩余集合，哪些依赖局部单调结构。