[eJOI 2020] Fountain (Day1)

题意

$N$ 个圆盘从上到下（编号 $1 \sim N$ ），第 $i$ 个圆盘直径 $D_i$ 、容量 $C_i$ 。圆盘里的水超过容量就会溢出，流入下方第一个直径更大的圆盘；下面没有更大的就流入水池。

$Q$ 次询问（互不影响）：向圆盘 $R$ 倒入 $V$ 体积的水，最后水停在哪？停在圆盘输出编号，流入水池输出 $0$ 。

数据范围： $N \leqslant 10^5$ ， $Q \leqslant 2 \times 10^5$ ， $C_i \leqslant 1000$ ， $D_i, V \leqslant 10^9$ 。

思路

一句话本质：每个圆盘的溢出去向是唯一且固定的——下方第一个直径更大的圆盘，与水量无关。于是喷泉变成若干条汇入水池的链，询问 = 沿链走、逐盘扣容量，问水在哪耗尽。这是"链上带权跳跃"，用单调栈求链 + 倍增段跳加速。

先看最直接的模拟：

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/**
 * 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-08-05 13:30
 * update_at: 2026-08-05 13:30
 */
// brute.cpp：小数据暴力解，O(n^2) 求每个圆盘的下一个更大直径，询问沿链模拟。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;

int n, q;
long long D[MAXN], C[MAXN];
int nxt[MAXN];

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

    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> D[i] >> C[i];

    // 直接向后找第一个直径更大的圆盘
    for (int i = 1; i <= n; i++) {
        nxt[i] = 0;
        for (int j = i + 1; j <= n; j++)
            if (D[j] > D[i]) {
                nxt[i] = j;
                break;
            }
    }

    for (int t = 0; t < q; t++) {
        int r;
        long long v;
        cin >> r >> v;

        int cur = r;
        long long need = v;
        while (true) {
            if (C[cur] >= need) {   // 当前圆盘装得下：停在这
                cout << cur << '\n';
                break;
            }
            need -= C[cur];         // 装满并溢出
            cur = nxt[cur];
            if (cur == 0) {         // 下面没有更大的圆盘：流入水池
                cout << 0 << '\n';
                break;
            }
        }
    }

    return 0;
}

暴力对每个询问从 $R$ 出发：装得下就停，装不下就扣掉容量、跳到下一个更大的圆盘。最坏 $O(N)$ 一个询问， $Q$ 次询问 $O(NQ)$ 不可行。

溢出去向是唯一的吗？

水从圆盘 $i$ 溢出后只会流向下方第一个 $D_j > D_i$ 的圆盘，这个去向只由 $i$ 决定，和倒了多少水无关。用单调栈从右往左 $O(N)$ 求出每个 $i$ 的 nxt[i]：

cpp

1
2
3while (stk_top > 0 && D[stk[stk_top]] <= D[i]) stk_top--;
nxt[i] = (stk_top > 0) ? stk[stk_top] : 0;   // 0 = 水池
stk[++stk_top] = i;

问题变成什么？

每个圆盘只有一个"父"（nxt[i]），整座喷泉是若干条指向水池（0）的链。询问 = 从 $R$ 出发沿链向上走，每经过一个圆盘扣掉它的容量 $C_i$ ，问水在哪耗尽——标准的"树上从节点向上走"场景，用倍增加速。

怎么加速沿链扣容量？

预处理两个倍增表：

up[k][i]：从 $i$ 沿链向上 $2^k$ 步到达的圆盘；
sum[k][i]：这 $2^k$ 步经过圆盘的容量和（含 $i$ ，不含终点）。

查询时从大到小枚举 $k$ ：只要 sum[k][cur] < need（跳过去这些圆盘都能被装满且水还有剩），就整段跳：

cpp

1
2
3
4
5
6for (int k = LOG - 1; k >= 0; k--) {
    if (up[k][cur] != 0 && sum[k][cur] < need) {
        need -= sum[k][cur];
        cur = up[k][cur];
    }
}

为什么跳完只剩两种情况？

循环停下的时刻，最小的 $k = 0$ 也不再满足 sum[0][cur] < need，即不再满足 C[cur] < need 或 up[0][cur] == 0：

C[cur] >= need：当前圆盘装得下剩余的水（含恰好装满，因为"大于容量才溢出"）→ 答案 cur；
否则说明 C[cur] < need 且 up[0][cur] == 0：当前圆盘也会装满，而它上面没有更大的圆盘 → 水流入水池，答案 0。

倍增正确性的数学证明

倍增的正确性来自二进制表示的唯一性：任意非负整数 $d$ 可以唯一写成若干个不同的 $2$ 的幂之和（ $d = \sum_k b_k 2^k$ ， $b_k \in \{0,1\}$ ）。"从大到小枚举 $2^k$ 、能跳就跳"的过程，就是逐位构造 $d$ 的二进制表示。

设从起点到答案需要走的距离为 $d$ ，当前已走距离为 $s$ （ $s \leqslant d$ ），归纳每一步：

若 $d$ 的第 $k$ 位是 $1$ ： $d - s$ 的剩余部分包含 $2^k$ 这一项，所以 $s + 2^k \leqslant d$ ，这一步仍然安全 → 跳， $s := s + 2^k$ ；
若 $d$ 的第 $k$ 位是 $0$ ：高位已经全部匹配， $d - s < 2^k$ ，所以 $s + 2^k > d$ ，这一步会越过答案 → 不跳。

由于每个 $2^k$ 在 $d$ 的二进制中至多出现一次，"能跳就跳"既不会跳过头，也不会漏跳，最终 $s = d$ 精确停在答案。

这个证明依赖两个前提，缺失则倍增失效：

单调性：check 必须满足 true…true false…false（安全位置是前缀）。本题沿链累计容量 sum[k][cur] 单调不减，恰好满足；
可分解性：距离能按二进制拆分，且跳跃表 up[k][i] = up[k-1][up[k-1][i]] 保证"跳 $2^k$ 步"等于"跳两次 $2^{k-1}$ 步"（归纳基础）。

对应到本题：剩余水量 need 就是 $d$ ，sum[k][cur] < need 就是"这一步安全"的 check，从 LOG-1 到 $0$ 枚举就是从高位到低位构造 need 的二进制路径。

代码

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/**
 * 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-08-05 13:30
 * update_at: 2026-08-05 14:00
 */
// 单调栈求每个圆盘的下一个更大直径（next 链），倍增维护跳跃表与容量前缀和。
// 查询与 rbook《倍增跳跃》模板同构：从大步到小步试探，能跳就跳。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
const int LOG = 20;

int n, q;
long long D[MAXN], C[MAXN];  // 直径、容量
int nxt[MAXN];               // nxt[i]：i 下方第一个 D 更大的圆盘，0 表示水池

int up[LOG][MAXN];           // up[k][i]：沿 next 链向上 2^k 步到达的圆盘
long long sum[LOG][MAXN];    // sum[k][i]：从 i 向上 2^k 步经过圆盘的容量和（含 i，不含终点）

int stk[MAXN], stk_top;      // 单调栈

// 查询：向圆盘 r 倒入 v 体积的水，返回水停下的圆盘编号（流入水池返回 0）。
// 从大步到小步试探：跳过的 2^k 个圆盘都能装满且水还有剩余，就整段跳过去。
int fountain_query(int r, long long v) {
    int cur = r;
    long long need = v;   // 剩余还需装下的水量

    for (int k = LOG - 1; k >= 0; k--) {
        int nxt_disk = up[k][cur];
        if (nxt_disk != 0 && sum[k][cur] < need) {
            need -= sum[k][cur];   // 这段圆盘全部装满
            cur = nxt_disk;
        }
    }

    // 跳不动时只有两种可能：
    // 1. cur 装得下剩余的水（含恰好装满，因为"大于容量才溢出"）→ 停在 cur
    // 2. cur 也会装满，而它上面没有更大的圆盘 → 流入水池
    return (C[cur] >= need) ? cur : 0;
}

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

    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> D[i] >> C[i];

    // 从右往左维护 D 严格递减的单调栈，栈顶就是第一个 D 更大的圆盘
    for (int i = n; i >= 1; i--) {
        while (stk_top > 0 && D[stk[stk_top]] <= D[i]) stk_top--;
        nxt[i] = (stk_top > 0) ? stk[stk_top] : 0;
        stk[++stk_top] = i;
    }

    // 倍增表：up[0][i] = 直接父，sum[0][i] = 自己的容量
    for (int i = 1; i <= n; i++) {
        up[0][i] = nxt[i];
        sum[0][i] = C[i];
    }
    for (int k = 1; k < LOG; k++)
        for (int i = 1; i <= n; i++) {
            up[k][i] = up[k - 1][up[k - 1][i]];
            sum[k][i] = sum[k - 1][i] + sum[k - 1][up[k - 1][i]];
        }

    for (int t = 0; t < q; t++) {
        int r;
        long long v;
        cin >> r >> v;
        cout << fountain_query(r, v) << '\n';
    }

    return 0;
}

复杂度

单调栈 $O(N)$ ，倍增表 $O(N \log N)$ ；每个询问 $O(\log N)$ 。总 $O((N + Q) \log N)$ ，空间 $O(N \log N)$ 。

总结

本题的建模关键是发现去向唯一：水往哪流由圆盘本身决定，于是过程变成静态的链，而不是动态模拟。链上的"走若干步、消耗带权和"问题，套路就是倍增。

以后看到"每个点只有一条出边 / 唯一的下一步去向"，先想到把过程变成链或森林，再用倍增跳段。

点权倍增 vs 边权倍增

本题的容量 $C_i$ 在点上（每个圆盘自己的容量），所以 sum[0][i] = C[i]，跳转判断 sum[k][cur] < need 时段的"消耗"含起点、不含终点。有些倍增题的信息在边上（如树上路径边权和、到根的距离），两类问题的结构相同，但语义和边界要区分：

	点权型（本题）	边权型（如树上距离）
信息存哪	节点自己的容量/权值	节点到父节点的边权
`sum[0][i]`	$C_i$	边权（或按定义约定）
时段语义	含起点 $i$ ，不含终点	通常含终点，不含起点
边界判断	`C[cur] >= need` 停	视题目约定（如 `>` / `>=`）

写法上 up[k][i] = up[k-1][up[k-1][i]]、sum[k][i] = sum[k-1][i] + sum[k-1][up[k-1][i]] 完全一样，但边界条件必须按信息在点还是边上重新核对，不能照搬。

图示解析

这张图展示样例圆盘的 next 链和一个询问的倍增跳段：

text

1
2
3
4
5
6
7
8
9
10圆盘 1..6 的 next 链（箭头指向下一个更大直径）

1(D4) → 2(D6) → 5(D10) → 0(水池)
3(D3) → 4(D4) → 5
6(D4) → 0

询问 (1, 25)：
  1(C10) ──装 10 剩 15──→ 2(C8) ──装 8 剩 7──→ 5(C9)
                                                   │
                                            剩 7 ≤ 9，停 5

读图方法：箭头就是"溢出去向"，每条链独立，终点要么是 0（水池）要么停在中途某盘。倍增做的事就是一次跳 $2^k$ 个圆盘，只关心"这段容量和 < 剩余水量"。