[TJOI2015] 旅游

形式化题目

给定一棵 $n$ 个点的树，每个点有一个价格。依次执行 $q$ 次操作，每次给出 $a, b, v$ ：

沿 $a \to b$ 的路径序列 $p_1, p_2, \dots, p_k$ （ $p_1 = a$ ， $p_k = b$ ），先选一个买入城市 $p_i$ ，再选一个卖出城市 $p_j$ （ $i < j$ ，买入必须先于卖出），利润为 $price[p_j] - price[p_i]$ ，输出最大利润，为负时输出 $0$ ；
路径上所有城市的价格同时增加 $v$ 。

解法路线

本题题面给出了真实的两档约束： $30\%$ 部分 $n \leqslant 100,\ q \leqslant 10^4$ ，满分部分 $n, q \leqslant 5 \times 10^4$ 。这两档不是同一算法的常数差别，而是价格序列的来源不同：部分分允许每次询问现场把路径取出来，满分要求路径操作必须在 $O(\log^2 n)$ 内完成。所以下面按递进方式组织：先把题意翻译成能跑的暴力，再把「枚举点对」换成「一次扫描」，最后把「现场取路径」换成「树剖 + 线段树」。

层次	适用约束	做法	复杂度	相对前层的推进
暴力	$n \leqslant 30$ （`brute.cpp` 的数组上限）	每次询问 BFS 取路径，枚举所有 $i < j$ 点对算利润，再逐点加价	$O(qn^2)$	基线
线性扫描	$n \leqslant 100,\ q \leqslant 10^4$ （对应 $30\%$ 测试点）	每次询问 DFS 取路径，沿路径一遍扫：边更新最低买入价边更新利润	$O(qn)$	复用「先取路径再沿路径处理」，把点对枚举换成单次扫描，消掉一个 $O(n)$ 因子；数组上限放宽到 $n \le 100$ ，完整覆盖 $30\%$ 子任务
正解	$n, q \leqslant 5 \times 10^4$	树链剖分把路径拆成 $O(\log n)$ 段 dfn 连续区间，线段树用四元摘要合并，区间加挂懒标记	$O((n + q)\log^2 n)$	复用「路径是一段有方向的序列」，用可合并摘要 + 懒标记消掉「每次询问现场遍历 $O(n)$ 个点」的瓶颈

满分档有两种写法，共用同一个四元摘要，差别只在树剖查询怎么攒方向：main.cpp 是「a 侧段拼在左边，走完统一翻转」，hld2.cpp 是「每段先翻成旅行方向，再追加到右边」。前者代码最短，后者中途状态可直接打印对照暴力解。

表里的关键跳跃是中间那一行到最后一行的跨越：前两层都无法避免每次询问把路径上的点真的走一遍。正解之所以能做到，是因为“最大利润”这个量对序列拼接是封闭的——一段序列只需要四个数就能完整参与合并。

暴力解法

适用范围

$n \leqslant 30$ ，受 brute.cpp 里 MAXN = 35 的数组上限所限。它的主要用途是把题意写成一份可执行的说明书，并作为对拍基准。

值得说清一点：本层并不是因为复杂度才过不了 $30\%$ 子任务。把数组上限放宽到 $105$ 后， $n = 100,\ q = 10^4$ 、每次询问都是整条链的最坏输入，实测约 $45$ ms（单线程、-O2、含读入）—— $O(qn^2)$ 在这个规模下恰好落在可接受范围。真正过不了的是满分档： $n$ 到 $5 \times 10^4$ 后，仅“每次把路径走一遍”就是 $2.5 \times 10^9$ 次操作。

思路

直接把题意翻译成程序：每次询问先用 BFS 在树上找到 $a \to b$ 的完整路径序列，然后枚举路径上所有满足 $i < j$ 的点对 $(p_i, p_j)$ ，用「先经过的 $p_i$ 买入、后经过的 $p_j$ 卖出」算利润并取最大值（小于 $0$ 时输出 $0$ ），最后把路径上每个城市的价格加 $v$ 。

这一层的价值在于它把题面最容易被误读的地方摆明了：利润带方向。brute.cpp 里枚举的每一对都写成 $i < j$ ，不是随便挑两个点算 $\max - \min$ 。若真按 $\max - \min$ 写，价格序列 [10, 1, 5] 会算出 $10 - 1 = 9$ ，但 10 在 1 前面，先买 10 再卖 1 只会亏，正确答案是 $0$ 。

代码

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/**
 * 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-12 22:28
 * update_at: 2026-08-12 22:29
 */
// brute.cpp：小数据暴力解，对每条路径直接枚举所有（买入城市，卖出城市）点对，辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 35;

int n, q;
long long price[MAXN];          // price[u] 城市 u 当前的宝石价格
vector<int> g[MAXN];            // 树的邻接表
int prev_node[MAXN];            // BFS 时记录的父链
int path[MAXN];                 // 还原出的 a -> b 路径序列
int path_len;                   // 路径长度（城市个数）

// 用 BFS 在树上求 a -> b 的路径，结果按旅行顺序放在 path[1..path_len]。
void get_path(int a, int b) {
    for (int i = 1; i <= n; i++) prev_node[i] = 0;
    queue<int> qq;
    qq.push(a);
    prev_node[a] = -1;
    while (!qq.empty()) {
        int u = qq.front();
        qq.pop();
        if (u == b) break;
        for (size_t i = 0; i < g[u].size(); i++) {
            int v = g[u][i];
            if (prev_node[v] != 0) continue;
            prev_node[v] = u;
            qq.push(v);
        }
    }
    // 从 b 沿父链回溯到 a，再反转得到 a -> b 顺序。
    int cnt = 0;
    for (int u = b; u != -1; u = prev_node[u]) {
        path[++cnt] = u;
    }
    for (int i = 1; i <= cnt / 2; i++) {
        swap(path[i], path[cnt + 1 - i]);
    }
    path_len = cnt;
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> price[i];
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    cin >> q;
    while (q--) {
        int a, b;
        long long v;
        cin >> a >> b >> v;
        get_path(a, b);

        // 枚举路径上的所有买卖点对：先经过的为买入城市，后经过的为卖出城市。
        long long best = 0; // 最大利润，至少为 0（不交易）
        for (int i = 1; i <= path_len; i++) {
            for (int j = i + 1; j <= path_len; j++) {
                long long profit = price[path[j]] - price[path[i]];
                if (profit > best) best = profit;
            }
        }
        cout << best << '\n';

        // ZJY 路过路径上每个城市，价格整体上涨 v。
        for (int i = 1; i <= path_len; i++) {
            price[path[i]] += v;
        }
    }

    return 0;
}

复杂度与瓶颈

时间：单次询问 BFS 取路径 $O(n)$ ，枚举点对 $O(k^2)$ （ $k$ 为路径长度，最坏 $n$ ），加价 $O(k)$ ，合计 $O(q n^2)$ 。
空间： $O(n)$ ，路径数组与价格数组都是 $n$ 级别。

瓶颈有两处。第一处很明显：枚举所有点对是 $O(k^2)$ ，而路径上真正的信息只有一个“到目前位置为止的最低买入价”，扫描一遍就够。第二处更本质：每次询问都要把路径上的点真的取出来，这一步是 $O(k)$ ， $q$ 次就是 $O(qn)$ ——即使把 $O(k^2)$ 优化掉，这个 $O(qn)$ 仍然过不了满分。下面的线性扫描先解决第一处，正解再解决第二处。

子任务解法：一次扫描代替点对枚举

适用范围

$n \leqslant 100$ ， $q \leqslant 10^4$ ，仍然是题面 $30\%$ 的部分分。

思路

观察到求最大利润只需要一个变量：走到当前位置之前的历史最低价。于是沿路径从头扫一遍，维护 $lowest$ （历史最低买入价）与 $best$ （当前最大利润），对每个位置 $p_i$ （ $i \geqslant 2$ ）：

best \leftarrow \max(best,\ price[p_i] - lowest),\qquad lowest \leftarrow \min(lowest,\ price[p_i])

顺序不能颠倒：必须先用之前的最低价算利润，再让当前位置尝试刷新最低价，否则会允许“同一个城市既买又卖”。初值取 $lowest = price[p_1]$ 、 $best = 0$ ，后者同时承担了“亏本就输出 $0$ ”的语义。

这一层仍然保留 DFS 现场取路径，所以复杂度只降了一个 $O(n)$ 因子；它的作用是把“求利润”这件事从 $O(k^2)$ 压到 $O(k)$ ，从而暴露出真正的瓶颈——取路径本身。

代码

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/**
 * 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-23 20:28
 * update_at: 2026-10-23 20:28
 */
// subtask_linear.cpp：对应 30% 子任务（n <= 100, q <= 10^4）的 O(qn) 解法。
// 每次询问先用 DFS 取出 a -> b 的完整路径，再沿路径扫一遍：边更新最低买入价边算利润。
// 相对 brute.cpp 的推进：把“枚举所有买卖点对”的 O(k^2) 换成一次 O(k) 扫描。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 105; // 30% 子任务 n <= 100

vector<int> g[MAXN]; // g[u]：与城市 u 直接相连的城市
ll price[MAXN];      // price[u]：城市 u 当前的宝石价格

int path[MAXN]; // path[1..path_len]：本次询问 a -> b 路径上依次经过的城市
int path_len;   // 路径上的城市个数

// 从 u 往 target 方向 DFS，把途经城市按旅行顺序写进 path[]。
// 返回值表示“u 的子树里找到了 target”，上层据此决定是否保留 u。
bool dfs_path(int u, int father, int target) {
    path[++path_len] = u;
    if (u == target) return true;
    for (int v : g[u]) {
        if (v == father) continue;
        if (dfs_path(v, u, target)) return true;
    }
    path_len--; // 这条分支没通向 target，退掉
    return false;
}

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

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> price[i];
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    int q;
    cin >> q;
    while (q--) {
        int a, b;
        ll v;
        cin >> a >> b >> v;

        path_len = 0;
        dfs_path(a, 0, b);

        // 一次扫描求最大利润：利润 = 当前价格 - 之前出现过的最低价格。
        ll best = 0;
        ll lowest = price[path[1]]; // 到目前位置为止最低的买入价
        for (int i = 2; i <= path_len; i++) {
            ll now = price[path[i]];
            if (now - lowest > best) best = now - lowest;
            if (now < lowest) lowest = now; // 更便宜的买点留给后面
        }
        cout << best << '\n';

        // 路过的城市价格整体上涨 v。
        for (int i = 1; i <= path_len; i++) price[path[i]] += v;
    }
    return 0;
}

复杂度与瓶颈

时间：单次询问 DFS 取路径 $O(n)$ ，扫描 $O(k)$ ，加价 $O(k)$ ，合计 $O(qn)$ 。最坏输入（ $n = 100$ 、 $q = 10^4$ 、每次都是整条链）实测约 $14$ ms，比同规模的枚举点对写法快约 3 倍（同一台机器、-O2、含读入）。
空间： $O(n)$ 。

瓶颈此时完全落在**“每次询问现场遍历路径”**上。 $O(qn)$ 在 $n = q = 5 \times 10^4$ 时是 $2.5 \times 10^9$ ，必然超时。要让路径操作变快，就必须回答两个问题：

一条树上路径能不能变成一个“区间”，交给擅长区间的数据结构？
那段数据结构要存什么，才能在 $O(1)$ 的合并里算出最大利润，并且支持整体加价？

第一个问题由树链剖分回答，第二个问题由下面的四元摘要回答。

正解（解法一）：两侧累积，最后统一翻转

树链剖分把路径拆成 $O(\log n)$ 段 dfn 连续区间，再用一棵线段树按 dfn 维护每段的摘要。这段摘要在树上要存什么，先退化成一维看最清楚。

先退化成一维：一个数组上的左买右卖

树上的路径不好直接下手，先压成一条线段。给定数组 $p_1, \dots, p_n$ ，每次问：在 $[l, r]$ 里选 $i < j$ ，让 $p_j - p_i$ 最大。整道题在树上做的事，只是把这个 $[l, r]$ 换成 $O(\log n)$ 段 dfn 区间。

单点的摘要。 只有一个价格 $p$ 的段，「左买右卖」无从谈起，于是记三元组

(min,\ max,\ best) = (p,\ p,\ 0)

其中 $min$ 是段内最低价、 $max$ 是最高价、 $best$ 是段内「先买后卖」能拿到的最大利润。单点没有两次买卖的机会，所以 $best = 0$ 。

合并两段。 设 $L$ 在左、 $R$ 在右。跨完整段的买卖只有三种落点：全在 $L$ 内、全在 $R$ 内、横跨两段。于是

min = \min(min_L, min_R),\qquad max = \max(max_L, max_R)

best = \max\big(best_L,\ best_R,\ max_R - min_L\big)

最后那一项 $max_R - min_L$ 是唯一的跨段候选，它天然满足「卖点在买点右边」——买价取自左段、卖价取自右段，位置顺序由拼接顺序保证，不需要另做判断。

建树与查询。 叶子放单点三元组，push_up 就是上面这组式子，整棵树 $O(n)$ 建完。区间查询把 $[l, r]$ 拆成 $O(\log n)$ 个节点，必须按原位顺序合并（左儿子先、右儿子后），答案取最终摘要的 $best$ 。

它和线性扫描是同一件事。 把合并式沿数组从左往右折一遍，每加入一个 $p_i$ ，累积摘要的 $min$ 记作 $lowest$ ，就有

best \leftarrow \max(best,\ p_i - lowest),\qquad lowest \leftarrow \min(lowest,\ p_i)

展开即 $best = \max_i \left(p_i - \min_{j<i} p_j\right)$ ，也就是「维护历史最低价」那遍扫描。两者没有分叉：扫描是现场折叠，线段树是把折叠结果预存起来。

为什么不能像前缀和那样 $O(1)$ 取任意区间。 加法有逆元，所以 $pre[r] - pre[l-1]$ 成立； $(min, max, best)$ 只有单位元和结合律，没有逆元—— $[1, r]$ 的最低价可能就落在 $[1, l-1]$ 里，把前半段去掉之后最低价变成什么，这部分信息已经丢了。所以这个结构只有两种用法： $O(n)$ 建线段树配 $O(\log n)$ 查询，或 $O(n\log n)$ 建 ST 表配 $O(1)$ 查询（且不支持修改）。本题每条询问后面还要整体加价，只能用前者。

回到树上只多一件事。 路径拆出的段并不都朝同一方向： $a$ 侧向上跳时拿到的那段，dfn 增序与旅行方向相反。要让一段「反着用」，就必须知道它在反方向上的 $best$ ，三元组因此扩成四元组。下面接着讲这个扩展。

关键观察

观察一：四元摘要对序列拼接封闭。 上一节的一维版本只要 $(min, max, best)$ 三个数。树上多出一条要求：同一段可能被反着走，所以还要存它在反方向上的利润。于是对一段价格序列，记四个数：

$minv$ ：段内最低价；
$maxv$ ：段内最高价；
$fwd$ （forward，正序）：按“先左后右”走过这段的最大利润（左边买、右边卖）；
$bwd$ （backward，反序）：按“先右后左”走过这段的最大利润（右边买、左边卖）。

按“先走完 $L$ 、再走完 $R$ ”的顺序拼接时，落点还是上一节那三种，只是两个方向各算一遍：

fwd = \max(fwd_L,\ fwd_R,\ maxv_R - minv_L)

bwd = \max(bwd_L,\ bwd_R,\ maxv_L - minv_R)

$minv, maxv$ 照常取 $\min / \max$ 。跨段项里只有一种方向可用：想在 $L$ 买、 $R$ 卖才符合“先买后卖”，反过来买在 $R$ 、卖在 $L$ 属于反序，只能算进 $bwd$ 。这就是买卖方向在合并里的唯一落点，也是为什么 $minv$ 和 $maxv$ 必须分开携带、不能只存一个差值。

字段	左段候选	右段候选	跨段候选
$minv$	$minv_L$	$minv_R$	—
$maxv$	$maxv_L$	$maxv_R$	—
$fwd$	$fwd_L$	$fwd_R$	$maxv_R - minv_L$
$bwd$	$bwd_L$	$bwd_R$	$maxv_L - minv_R$

观察二：整体加价只平移最值。 一段里所有价格同加 $v$ ， $minv$ 与 $maxv$ 各加 $v$ ，任意两点之差 $price_j - price_i$ 不变，所以 $fwd$ 、 $bwd$ 都不变。于是区间加可以做成懒标记：命中整段时只改 $minv, maxv$ 和标记，两个利润字段原样保留。

观察三：翻转方向只需交换 $fwd$ 与 $bwd$ 。 把一段的旅行方向倒过来， $minv, maxv$ 不变，正序利润变反序利润，反之亦然。

思路

把上面三点拼起来：

树链剖分把 $a \to b$ 的路径拆成 $O(\log n)$ 段，每段在 dfn 上是连续区间。同一条重链上 dfn 随深度递增。
线段树按 dfn 建树，每个节点存四元摘要，支持区间加与区间摘要查询。查询返回的摘要按 dfn 增序排列，也就是“先高处、后低处”。
方向修正。 $a$ 一侧向上跳时取出的区间 $[dfn[top], dfn[x]]$ 的 dfn 增序是“从链头到 $x$ ”，而真实旅行方向是“从 $x$ 到链头”，两者相反，所以这一侧要按逆序累积； $b$ 一侧取出的区间 $[dfn[top], dfn[y]]$ 的 dfn 增序恰是“从链头到 $y$ ”，与旅行方向一致，按正序累积。
具体实现上， $a$ 一侧每次把新区间拼在累积结果的左边（up = merge(新区间, up)），走完后整段是逆旅行顺序，最后 flip 一次就得到 $a \to$ LCA 的正向摘要； $b$ 一侧每次把新区间拼在左边，得到 LCA $\to b$ 的正向摘要。最终答案是 merge(flip(up), down).fwd，取 $\max(0, \cdot)$ 后输出。
输出后调用路径加，把 $v$ 加到路径上每一段。

第 3 步是全文最容易写错的地方，下面用一棵小树（不是题面样例）把它摊开。左半边是树与剖分结果， $a = 5$ 、 $b = 3$ ；右半边把同一信息摆成 dfn 数组，用 ①②③ 标出这条路径被拆成的三段。

图的读法：

链 1 是 $1 \to 2 \to 4 \to 6$ ，dfn 连续取到 $1..4$ ，且越深 dfn 越大；链 5 与链 3 各只有一个点。
$a = 5$ 挂在链 1 的节点 2 下面，所以 $a$ 侧要先取链 5 的一段（①），再取链 1 的区间 $[1,2]$ （②）——这就是 $a$ 侧跨两条重链的情形。
② 的 dfn 增序是 $1 \to 2$ （高处到低处），真实旅行方向是 $2 \to 1$ ，两者相反，必须翻转；③ 是单点，方向无影响。
蓝色框里是累积过程： $a$ 侧先得到 $(5)$ ，并入 ② 的翻转后是 $(5,2,1)$ ； $b$ 侧是 $(3)$ 。两段拼起来才是 $(5,2,1,3)$ 。若把 ② 放到 ① 前面，序列变成 $(2,1,5)$ ，答案就错了。

代码

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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226/**
 * 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-23 20:21
 * update_at: 2026-10-23 20:21
 */
// main.cpp：树链剖分把路径拆成 O(log n) 段 dfn 连续区间，
// 线段树用四元摘要 (minv, maxv, fwd, bwd) 维护“带方向的买卖最大利润”，并支持区间加。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 50005;

vector<int> g[MAXN]; // g[u]：与城市 u 直接相连的城市

int n, q;
ll price[MAXN];   // price[u]：城市 u 当前的宝石价格
ll ordered[MAXN]; // ordered[dfn[u]]：按 dfn 重排后的价格，用来建线段树

// 一段价格序列的四元摘要（序列天然按 dfn 增序，即“先到左端、后到右端”）：
// minv / maxv：段内最小 / 最大价格
// fwd（forward）：按“先左后右”走过这段时能获得的最大利润（左边买、右边卖）
// bwd（backward）：按“先右后左”走过这段时能获得的最大利润（右边买、左边卖）
struct Info {
    ll minv, maxv, fwd, bwd;
};

// 空段（合并的单位元）：不含城市，最值取到不可能的值，利润为 0。
Info empty_info() {
    return Info{LLONG_MAX / 4, LLONG_MIN / 4, 0, 0};
}

// 按“先走完 a 段、再走完 b 段”的顺序合并两段摘要。
Info merge_info(const Info &a, const Info &b) {
    Info c;
    c.minv = min(a.minv, b.minv);
    c.maxv = max(a.maxv, b.maxv);
    // 正序买卖：全在 a 内、全在 b 内，或在 a 买、在 b 卖。
    c.fwd = max(max(a.fwd, b.fwd), b.maxv - a.minv);
    // 反序买卖：全在 a 内、全在 b 内，或在 b 买、在 a 卖。
    c.bwd = max(max(a.bwd, b.bwd), a.maxv - b.minv);
    return c;
}

// 把这一段的旅行方向倒过来：最值不变，正序与反序利润互换。
Info flip_info(const Info &a) {
    return Info{a.minv, a.maxv, a.bwd, a.fwd};
}

// ---------------- 线段树：维护四元摘要 + 区间加 ----------------

ll seg_minv[MAXN << 2]; // 节点区间的最小价格
ll seg_maxv[MAXN << 2]; // 节点区间的最大价格
ll seg_fwd[MAXN << 2];  // 节点区间按 dfn 增序的最大利润
ll seg_bwd[MAXN << 2];  // 节点区间按 dfn 减序的最大利润
ll lazy[MAXN << 2];     // 区间加懒标记

// 区间整体加 value：最值一起平移，两个方向的利润不变。
void apply_add(int p, ll value) {
    seg_minv[p] += value;
    seg_maxv[p] += value;
    lazy[p] += value;
}

void pull(int p) {
    Info c = merge_info(Info{seg_minv[p << 1], seg_maxv[p << 1], seg_fwd[p << 1], seg_bwd[p << 1]},
                        Info{seg_minv[p << 1 | 1], seg_maxv[p << 1 | 1], seg_fwd[p << 1 | 1], seg_bwd[p << 1 | 1]});
    seg_minv[p] = c.minv;
    seg_maxv[p] = c.maxv;
    seg_fwd[p] = c.fwd;
    seg_bwd[p] = c.bwd;
}

void push(int p) {
    if (lazy[p] == 0) return;
    apply_add(p << 1, lazy[p]);
    apply_add(p << 1 | 1, lazy[p]);
    lazy[p] = 0;
}

void build(int p, int l, int r) {
    if (l == r) {
        seg_minv[p] = seg_maxv[p] = ordered[l];
        seg_fwd[p] = seg_bwd[p] = 0;
        return;
    }
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    pull(p);
}

void range_add(int p, int l, int r, int ql, int qr, ll value) {
    if (ql <= l && r <= qr) {
        apply_add(p, value);
        return;
    }
    push(p);
    int mid = (l + r) >> 1;
    if (ql <= mid) range_add(p << 1, l, mid, ql, qr, value);
    if (qr > mid) range_add(p << 1 | 1, mid + 1, r, ql, qr, value);
    pull(p);
}

// 查询 [ql, qr] 的摘要，返回的行内顺序就是 dfn 增序。
Info range_query(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return Info{seg_minv[p], seg_maxv[p], seg_fwd[p], seg_bwd[p]};
    }
    push(p);
    int mid = (l + r) >> 1;
    if (qr <= mid) return range_query(p << 1, l, mid, ql, qr);
    if (ql > mid) return range_query(p << 1 | 1, mid + 1, r, ql, qr);
    return merge_info(range_query(p << 1, l, mid, ql, qr),
                      range_query(p << 1 | 1, mid + 1, r, ql, qr));
}

// ---------------- 树链剖分 ----------------

int parent[MAXN];    // parent[u]：u 的父亲
int depth[MAXN];     // depth[u]：u 的深度
int siz[MAXN];       // siz[u]：以 u 为根的子树大小
int heavy[MAXN];     // heavy[u]：u 的重儿子，没有则为 0
int chain_top[MAXN]; // chain_top[u]：u 所在重链的链头
int dfn[MAXN];       // dfn[u]：u 的新编号，同一条重链上连续
int timer = 0;

// 第一次 DFS：求父亲、深度、子树大小和重儿子。
void dfs_size(int u, int father) {
    parent[u] = father;
    depth[u] = depth[father] + 1;
    siz[u] = 1;
    heavy[u] = 0;
    for (int v : g[u]) {
        if (v == father) continue;
        dfs_size(v, u);
        siz[u] += siz[v];
        if (heavy[u] == 0 || siz[v] > siz[heavy[u]]) heavy[u] = v;
    }
}

// 第二次 DFS：先走重儿子，保证每条重链的 dfn 连续。
void dfs_decompose(int u, int chain_head) {
    chain_top[u] = chain_head;
    dfn[u] = ++timer;
    ordered[timer] = price[u];
    if (heavy[u] != 0) dfs_decompose(heavy[u], chain_head);
    for (int v : g[u]) {
        if (v == parent[u] || v == heavy[u]) continue;
        dfs_decompose(v, v);
    }
}

// 查询从 a 走到 b 沿旅行方向的四元摘要。
Info path_query(int a, int b) {
    // up 累积 a 一侧（向上走的那些段），存成“逆旅行顺序”；
    // down 累积 b 一侧（向下走的那些段），存成旅行顺序。
    Info up = empty_info();
    Info down = empty_info();
    int x = a, y = b;
    while (chain_top[x] != chain_top[y]) {
        if (depth[chain_top[x]] >= depth[chain_top[y]]) {
            // 链头 dfn 小、x 的 dfn 大，所以 [dfn[top], dfn[x]] 的 dfn 增序是“高处 -> 低处”，
            // 正好是逆向旅行顺序，直接拼在 up 前面。
            up = merge_info(range_query(1, 1, n, dfn[chain_top[x]], dfn[x]), up);
            x = parent[chain_top[x]];
        } else {
            // b 一侧这一段 [dfn[top], dfn[y]] 的 dfn 增序就是旅行顺序（链头 -> y），拼在 down 前面。
            down = merge_info(range_query(1, 1, n, dfn[chain_top[y]], dfn[y]), down);
            y = parent[chain_top[y]];
        }
    }
    // 最后两点在同一条重链上，把剩下的那一段也收进去。
    if (depth[x] >= depth[y]) {
        up = merge_info(range_query(1, 1, n, dfn[y], dfn[x]), up);
    } else {
        down = merge_info(range_query(1, 1, n, dfn[x], dfn[y]), down);
    }
    // up 存的是逆旅行顺序，翻转一次就得到 a 到 LCA 的正向摘要。
    return merge_info(flip_info(up), down);
}

// 路径 a -> b 上所有城市的价格同时加 value。
void path_add(int a, int b, ll value) {
    int x = a, y = b;
    while (chain_top[x] != chain_top[y]) {
        if (depth[chain_top[x]] < depth[chain_top[y]]) swap(x, y);
        range_add(1, 1, n, dfn[chain_top[x]], dfn[x], value);
        x = parent[chain_top[x]];
    }
    if (depth[x] > depth[y]) swap(x, y);
    range_add(1, 1, n, dfn[x], dfn[y], value);
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> price[i];
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs_size(1, 0);
    dfs_decompose(1, 1);
    build(1, 1, n);

    cin >> q;
    while (q--) {
        int a, b;
        ll v;
        cin >> a >> b >> v;
        // 先按旅行方向问最大利润（亏本输出 0），再给路径整体加价。
        Info res = path_query(a, b);
        cout << max(0LL, res.fwd) << '\n';
        path_add(a, b, v);
    }
    return 0;
}

复杂度

时间：两次 DFS 预处理 $O(n)$ ，建树 $O(n)$ ；单次操作跳 $O(\log n)$ 条重链，每条链上一次线段树查询或修改 $O(\log n)$ ，故单次 $O(\log^2 n)$ ，总计 $O((n + q)\log^2 n)$ 。
空间：线段树四个摘要数组与懒标记各 $4n$ ，树剖数组与邻接表 $O(n)$ ，合计 $O(n)$ 。

解法二：每段立即翻向，再追加到右边

思路

解法一和 hld2.cpp 用的是同一个四元摘要、同一套合并式、同一棵线段树，差别只在树剖查询里怎么攒方向。

解法一把 $a$ 侧的每一段拼在累积器左边（up = merge(段, up)），所以累积器存的是逆旅行顺序，全部跳完再 flip 一次变正。全程只翻转一次，代价是中途状态不能直接读。

解法二把 $a$ 侧的每一段先翻成旅行方向，再追加到右边（left = merge(left, flip(段))）。累积器的每一步都已经是“从 $a$ 出发、按真实旅行顺序”的摘要，任何时候打印出来都能和暴力解的路径序列直接对照。代价是 $a$ 侧每段多一次 flip，而 flip 只是交换两个 ll，开销可以忽略。

$b$ 侧两种写法完全一样：区间 $[dfn[top[y]], dfn[y]]$ 的 dfn 增序就是链头 $\to y$ ，正是旅行方向，前插到左边即可。

上面的方向图解对两套写法都成立：①②③ 的分段与方向不变，变的只是 ① 和 ② 拼进累积器的位置。

代码按 rbook 模板 hld 的全局数组写法组织，分成 sgt 段和 hld 段：sgt 段只管 base[1..n] 上的摘要与懒标记，hld 段负责把路径拆成 dfn 区间。

代码

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
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239/**
 * 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-29 17:40
 * update_at: 2026-10-29 17:40
 */
// hld2.cpp：解法二，树链剖分 + 线段树（四元摘要），按 rbook hld 模板的全局数组写法组织。
// 与 main.cpp 用同一个摘要和同一套合并式，差别只在「树剖查询的方向怎么攒」：
//   main.cpp：a 侧每段拼在累积器左边，全部走完后再统一 flip 一次；
//   本文件  ：每段先 flip 成真实旅行方向（x → 链头），再追加到累积器右边。
// 两种写法等价，本文件的好处是累积器每一步都已经是"从 a 出发、按旅行顺序"的摘要，
// 中途断点打印出来就能直接和暴力解对照，方向写错时更容易定位。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int maxn = 50000 + 5;
const ll BIG = (ll)1e18; // 空段的最值用 ±BIG，保证不参与任何取最值

int n, q;

/*------------------------ sgt 代码 开始 ------------------------*/
// 线段树维护数组 base[1..n]，每个节点存一段价格序列的四元摘要：
//   mn / mx：段内最低 / 最高价
//   fwd（forward）  ：按 dfn 增序（先左后右）走过这段的最大利润
//   bwd（backward） ：按 dfn 减序（先右后左）走过这段的最大利润
ll base[maxn];
ll mn[maxn << 2];
ll mx[maxn << 2];
ll fwd[maxn << 2];
ll bwd[maxn << 2];
ll lz[maxn << 2]; // 区间加懒标记

int ls(int p) { return p << 1; }     // p 的左儿子 2p
int rs(int p) { return p << 1 | 1; } // p 的右儿子 2p+1

// 一段摘要
struct Info {
    ll mn, mx, fwd, bwd;
};

Info make_info(ll a, ll b, ll c, ll d) { return Info{a, b, c, d}; }

// 空段：不含任何城市
Info empty_info() { return Info{BIG, -BIG, 0, 0}; }

// 按「先走完 a、再走完 b」的顺序合并
Info join_info(Info a, Info b) {
    Info c;
    c.mn = min(a.mn, b.mn);
    c.mx = max(a.mx, b.mx);
    c.fwd = max(max(a.fwd, b.fwd), b.mx - a.mn); // 要么全在一边，要么左买右卖
    c.bwd = max(max(a.bwd, b.bwd), a.mx - b.mn); // 要么全在一边，要么右买左卖
    return c;
}

// 把一段的旅行方向倒过来：最值不变，两个方向的利润互换
Info flip_info(Info a) { return Info{a.mn, a.mx, a.bwd, a.fwd}; }

Info seg_info(int p) { return Info{mn[p], mx[p], fwd[p], bwd[p]}; }

// 整段加 value：最值一起平移，两个方向的利润是差值，保持不变
void apply_add(int p, ll value) {
    mn[p] += value;
    mx[p] += value;
    lz[p] += value;
}

void push_up(int p) {
    Info c = join_info(seg_info(ls(p)), seg_info(rs(p)));
    mn[p] = c.mn;
    mx[p] = c.mx;
    fwd[p] = c.fwd;
    bwd[p] = c.bwd;
}

void push_down(int p) {
    if (lz[p] == 0) return;
    apply_add(ls(p), lz[p]);
    apply_add(rs(p), lz[p]);
    lz[p] = 0;
}

void seg_build(int p, int l, int r) {
    lz[p] = 0;
    if (l == r) {
        mn[p] = mx[p] = base[l];
        fwd[p] = bwd[p] = 0; // 单个城市无法买卖
        return;
    }
    int mid = (l + r) >> 1;
    seg_build(ls(p), l, mid);
    seg_build(rs(p), mid + 1, r);
    push_up(p);
}

// 区间加
void range_add(int ql, int qr, ll value, int p, int l, int r) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
        apply_add(p, value);
        return;
    }
    push_down(p);
    int mid = (l + r) >> 1;
    range_add(ql, qr, value, ls(p), l, mid);
    range_add(ql, qr, value, rs(p), mid + 1, r);
    push_up(p);
}

// 区间摘要查询：返回的摘要按 dfn 增序（l → r）
Info range_query(int ql, int qr, int p, int l, int r) {
    if (qr < l || r < ql) return empty_info();
    if (ql <= l && r <= qr) return seg_info(p);
    push_down(p);
    int mid = (l + r) >> 1;
    return join_info(range_query(ql, qr, ls(p), l, mid),
                     range_query(ql, qr, rs(p), mid + 1, r));
}
/*------------------------ sgt 代码 结束 ------------------------*/

/*------------------------ hld 代码 开始 ------------------------*/
// 树链剖分：g 存树，6 个核心数组维护树上信息。
vector<int> g[maxn];
ll price[maxn]; // price[u]：城市 u 的当前价格（只用于建树时搬进 base）

int fa[maxn];  // fa[u]：父亲，根的 fa 为 0
int dep[maxn]; // dep[u]：深度，根为 1
int sz[maxn];  // sz[u]：子树大小（含自己）
int son[maxn]; // son[u]：重儿子，叶子为 0
int top[maxn]; // top[u]：所在重链的链头
int dfn[maxn]; // dfn[u]：线段树上的位置（DFS 新编号）
int timer;

void add_edge(int u, int v) {
    g[u].push_back(v);
    g[v].push_back(u);
}

// 第一遍 DFS：往下求 fa、dep，回溯时汇总 sz 并选出重儿子 son
void dfs1(int u, int father) {
    fa[u] = father;
    dep[u] = dep[father] + 1;
    sz[u] = 1;
    son[u] = 0;
    for (int v : g[u]) {
        if (v == father) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v;
    }
}

// 第二遍 DFS：重儿子优先分配 dfn，保证重链连续且链内 dfn 随深度递增
void dfs2(int u, int head) {
    top[u] = head;
    dfn[u] = ++timer;
    base[timer] = price[u];
    if (son[u]) dfs2(son[u], head);
    for (int v : g[u]) {
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

void build(int root) {
    dfs1(root, 0);
    timer = 0;
    dfs2(root, root);
    seg_build(1, 1, n);
}

// a → b 整个路径的摘要，按真实旅行顺序（a 先、b 后）。
// a 侧向上走：区间 [dfn[top], dfn[x]] 的 dfn 增序是 top → x，与旅行方向相反，先 flip 再追加到右边；
// b 侧向下走：区间 [dfn[top], dfn[y]] 的 dfn 增序就是 top → y，正是旅行方向，直接前插到左边。
Info path_info(int a, int b) {
    Info left = empty_info();  // 已走过的 a 侧部分，始终是"从 a 出发"的顺序
    Info right = empty_info(); // 已收集的 b 侧部分，始终是"朝 b 去"的顺序
    int x = a, y = b;
    while (top[x] != top[y]) {
        if (dep[top[x]] >= dep[top[y]]) {
            left = join_info(left, flip_info(range_query(dfn[top[x]], dfn[x], 1, 1, n)));
            x = fa[top[x]];
        } else {
            right = join_info(range_query(dfn[top[y]], dfn[y], 1, 1, n), right);
            y = fa[top[y]];
        }
    }
    // 两点落在同一条重链上：x、y 中较深的那个先被走过
    if (dep[x] >= dep[y]) {
        left = join_info(left, flip_info(range_query(dfn[y], dfn[x], 1, 1, n)));
    } else {
        right = join_info(range_query(dfn[x], dfn[y], 1, 1, n), right);
    }
    return join_info(left, right);
}

// 路径上所有城市的价格同时加 value
void path_add(int a, int b, ll value) {
    int x = a, y = b;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        range_add(dfn[top[x]], dfn[x], value, 1, 1, n);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    range_add(dfn[x], dfn[y], value, 1, 1, n);
}
/*------------------------ hld 代码 结束 ------------------------*/

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

    cin >> n;
    for (int u = 1; u <= n; ++u) g[u].clear();
    for (int i = 1; i <= n; i++) cin >> price[i];
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
    }

    build(1); // 根固定为 1

    cin >> q;
    while (q--) {
        int a, b;
        ll v;
        cin >> a >> b >> v;
        // 先按旅行方向问最大利润（亏本输出 0），再给路径整体加价
        Info res = path_info(a, b);
        cout << max(0LL, res.fwd) << '\n';
        path_add(a, b, v);
    }

    return 0;
}

复杂度

与解法一完全相同：预处理 $O(n)$ ，单次 $O(\log^2 n)$ ，总计 $O((n + q)\log^2 n)$ ，空间 $O(n)$ 。实测 $n = q = 5 \times 10^4$ （-O2、cin 关闭同步、含读入）：随机树上 main.cpp 约 $0.3$ s，本写法约 $0.5$ s；链上两者都约 $0.05$ s。差的是传摘要结构体的常数，不是复杂度。

一个容易踩的方向坑

$a$ 侧的 join 参数顺序只有一种写法：join(累积器, flip(新段))，新段永远在右边。写成 join(flip(新段), 累积器) 就把段序颠倒了。

这个错很隐蔽，因为样例 2 里 $a$ 侧每次都只跨一条重链（单段时顺序不影响），两套写法输出完全一致；只有 $a$ 侧需要跨两条以上重链的数据才会暴露。拿 gen.py 随机对拍到第 69 组就出现了 61 与 10 的差异。想手动验证的话，构造一棵 $a$ 位于轻链底部、 $b$ 在另一侧的树就够了。

总结

本题的骨架是“路径上的方向性统计 + 区间加”。三个技术点各自解决一个具体障碍：

买卖有方向 ⇒ 摘要必须同时携带正序与反序两个利润，只存 $\max$ 与 $\min$ 会在 [10, 1, 5] 这类序列上给出错误答案；
路径不是数组区间 ⇒ 树链剖分把路径拆成 $O(\log n)$ 段 dfn 连续区间，代价是必须处理每一段的方向；
价格整体上浮 ⇒ 差值不变，于是懒标记只需平移最值。

把本题与同族题目对照：区间加 + 单点 / 区间和的题（如 P1438）摘要只有一个数，方向无关；P3870 那类区间翻转题的懒标记要在“摘要的自同态”上做文章。本题的特殊之处在于摘要本身就带方向，因此树剖拆段时必须做方向翻转——漏掉它， $fwd$ 就不再表示“先买后卖的利润”。解法一选择“先逆序攒、最后翻一次”，解法二选择“每段立刻翻正再追加”，两种都把这一步安排在了明面上。

图示解析

下面这张 ASCII 图展示三层解法之间的推进关系，重点标出每层消除的瓶颈：

text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22暴力（brute.cpp）
  每次询问 BFS 取路径 -> 枚举所有 i<j 点对 -> 逐点加价
  单次 O(k^2)，总计 O(q*n^2)
        |
        | 瓶颈一：点对枚举是多余的，最大利润只需一个「历史最低价」
        v
一次扫描（subtask_linear.cpp）
  每次询问 DFS 取路径 -> 沿路径一遍扫（边更新最低价边更新利润）-> 逐点加价
  单次 O(k)，总计 O(q*n)，30% 子任务可过
        |
        | 瓶颈二：每次询问仍要把路径上的点真的走一遍
        v
树剖 + 线段树（main.cpp / hld2.cpp）
  路径拆成 O(log n) 段 dfn 连续区间
  每段用四元摘要 (minv, maxv, fwd, bwd)，拼接时 O(1) 合并
  整体加价只平移 minv/maxv -> 懒标记可用
  a 侧段的方向处理：main.cpp 逆序累积后 flip 一次；hld2.cpp 每段先 flip 再追加
  b 侧段按正序累积
  答案 = max(0, fwd)，随后路径区间加 v
        |
        v
总计 O((n + q) log^2 n)，空间 O(n)

图中的两处瓶颈标注对应两次真正的跨越：第一次把 $O(k^2)$ 压成 $O(k)$ ，第二次把“现场走路径”换成“合并摘要”。最需要记住的是最后一段的方向处理——路径查询写错几乎都出在这里，main.cpp 和 hld2.cpp 只是把这一步放在不同位置：一个是最后统一翻，一个是每段立刻翻。

参考与致谢

本题思路与公开题解对照后采用，正文与代码均为本项目自行撰写。以下题解帮助确认了「四元摘要」这一主流路线及其各种合并写法：

作者（uid）	题解标题	原链接	本文参考了什么
TKXZ133（uid 767096）	旅游题解	https://www.luogu.com.cn/article/bh5jl6xc	「 $a$ 侧段把新区间拼在累积结果左边、 $b$ 侧段同样拼左边，最后直接合成」这一种最少分支的树剖查询写法；本文 `path_query` 的累积顺序与它一致
MeowScore（uid 140360）	P3976题解	https://www.luogu.com.cn/article/mdfbnf5t	「起点侧取反序、终点侧取正序，最终答案由两段跨接」的直觉解释；四元字段各自的合并式
devout（uid 97344）	题解 P3976 【[TJOI2015]旅游】	https://www.luogu.com.cn/article/m18gzifi	确认「只维护 $\max/\min$ 会因方向而错」的动机叙述
Genius_Z（uid 110271）	P3976 旅游 LCT	https://www.luogu.com.cn/article/2ipib0sa	对照了 LCT 路线（用 `reverse` 交换正反序利润）；本文最终未采用，理由见下

内容	来源
四元摘要的合并公式与「整体加价只平移最值」	公开题解中普遍出现，本文独立复核
树剖查询的累积顺序与 `flip` 语义	参照 bh5jl6xc 的结构，本文重新推导并独立验证
`brute.cpp`、`subtask_linear.cpp`、`main.cpp`、`hld2.cpp` 全文与逐行注释	本项目自行编写
三层复杂度分析、每层瓶颈定位、边界情形讨论	本项目自行推导

补充说明：公开题解中另有 LCT 写法（如 2ipib0sa），代码量与本方案相当但需要额外掌握 LCT 的 access / makeroot / split 与虚子树无关的翻转标记，对读者前置要求更高；还有若干篇的树剖查询分支多达四类（如 nladyknp），实现更长。因此本文选择「树剖 + 四元摘要 + 两侧累积」这一路线作为主解。

目录

形式化题目

解法路线

暴力解法

适用范围

思路

代码

复杂度与瓶颈

子任务解法：一次扫描代替点对枚举

适用范围

思路

代码

复杂度与瓶颈

正解（解法一）：两侧累积，最后统一翻转

先退化成一维：一个数组上的左买右卖

关键观察

思路

代码

复杂度

解法二：每段立即翻向，再追加到右边

思路

代码

复杂度

一个容易踩的方向坑

总结

图示解析

参考与致谢