剥开文艺外壳：前缀和后缀和优化分段贡献最大值问题-育师

1. 拿到题目先别写代码，先把“故事”剥掉

1.1 为什么文艺标题总要配一个奇怪的模型

看到“P8590 『JROI-8』这是新历的朝阳，也是旧历的残阳”这个标题时，我正在翻题单。第一反应是：这怕是又一道把语文和算法绑在一起的题。“新历”“旧历”“朝阳”“残阳”，四个词摆在一起，明显在暗示一件事——存在一个分界点，分界点两边的时间规则不一样。做竞赛题多了就会发现，越是这种带文学包装的标题，底下越藏着一个“分段计算”或者“分段规则”的模型。

拿到这种题，心态特别容易崩的同学会直接盯着题面里的故事看半天，试图从“新历”“旧历”里读出点隐藏条件。我的经验是反过来的：先把故事放一边，直接去数据范围、输入格式和“求什么”下手。因为无论题目把背景写得多么诗意，最后落回来的无非是数组、区间、前缀、后缀、最值这些老面孔。标题的作用不是为了提供线索，而是告诉我们：这个题大概率要你“选一个位置，两侧按不同方式贡献”。

1.2 一个用于讲解的简化模型

说实话，原题的完整细节我不打算在这里逐字复述，因为复盘类文章最重要的不是让你照着抄一遍原题，而是把一类题的思考路径留下来。为了方便讲解，我把题目核心抽象成下面这样一个简化模型，你只要看懂了它，再看原题就会觉得“原来是这么回事”。

给定一个长度为 n 的正整数序列 a[1..n]，要求选一个分割点 x，把序列切成左右两段。左侧（旧历部分）的第 i 个元素贡献为 (i - 1) × a[i]，右侧（新历部分）的第 i 个元素贡献为 (n - i) × a[i]。最终答案是：

f(x) = Σ_{i=1}^{x} (i-1)·a[i] + Σ_{i=x+1}^{n} (n-i)·a[i]

要求最大化这个 f(x)。

这个模型怎么理解？左侧权重 (i-1) 意味着在“旧历”那一边，越靠近结尾的元素权重越大，就像一段历史残影，越接近落幕越沉重；右侧权重 (n-i) 则是越靠近开头权重越大，像朝阳初升，刚登场的影响最盛。你把 x 当作新旧历法交接的那一天，整个式子就是在求一个“交替时刻”，让整体影响最大。

这个抽象版本和很多实际题目的思想是一致的，只是具体系数和限制条件可能不同。读题时要做的事，就是把题面里一堆修饰语全部换成这种干净的数学符号。

1.3 先写暴力，再优化：竞赛铁律

我说句得罪人的话：很多同学一看到这种题就开始想贪心怎么办、DP怎么写，结果想了半小时没结果，心态直接崩掉。正确的顺序永远是先写一个最暴力、最无脑的枚举，再在这个基础上谈优化。

暴力是什么？枚举每个可能的 x，从 1 到 n-1，每次重新累加两边。复杂度 O(n²)，n 在几百的时候完全没问题。代码写起来也快，十分钟能搞定。你要用它做什么？第一，验证自己对题面的理解是不是对的；第二，作为后续优化的“标准答案”，代码写错了能对拍；第三，让你在推导优化时有个具体的数据结构可以参考，不会飘。

我一直跟身边的朋友说：暴力不是丢人的，暴力是你手里最可靠的那把尺子。一道题难不难，先看你能否写出一个“正确但慢”的版本。能写出来，说明题目读懂了；接下来才是考虑怎么变快。

2. 核心式子的推导：从 O(n²) 到 O(n)

2.1 拆开式子：前缀和后缀各管一边

回到 f(x) 这个式子。表面上，枚举 x 之后还要遍历两段数组，所以看起来是 O(n²)。但你把两个求和符号分开看，立刻能发现端倪。

左边的 Σ_{i=1}^{x} (i-1)·a[i] 只跟前缀有关。如果我用一个数组 W1[x] 表示“从第一个元素到第 x 个元素，按照 (i-1) 加权的和”，那么左边这一整块就等价于 W1[x]。

右边的 Σ_{i=x+1}^{n} (n-i)·a[i] 只跟后缀有关。同理，用 W2[x+1] 表示“从第 x+1 个元素到第 n 个元素，按照 (n-i) 加权的和”，右边这一整块就是 W2[x+1]。

于是 f(x) 直接变成：

f(x) = W1[x] + W2[x+1]

这个转化看起来平平无奇，但它把复杂度从“每次枚举都要重新扫数组”降成了“提前预处理，枚举时 O(1) 查询”。怎么预处理呢？ W1 可以顺着扫一遍：

W1[i] = W1[i-1] + (i-1) × a[i]

W2 就得从右往左扫，注意下标的语义。W2[i] 表示从 i 到 n 的加权和，边界是 W2[n+1] = 0，然后：

W2[i] = W2[i+1] + (n-i) × a[i]

这样一来，整个算法的复杂度就是 O(n) 预处理，加上 O(n) 枚举 x，总共 O(n)，空间 O(n)。n 到 1e6 也完全不虚。

2.2 差分视角：看看 f(x) 到底长什么样

做到 O(n) 其实已经能过题了，但你别急着收手。我习惯再往下推一步，看看 f(x) 本身有没有什么结构。把相邻两个位置做差：

f(x+1) - f(x) = (W1[x+1] + W2[x+2]) - (W1[x] + W2[x+1])

展开之后，W1 的增量是 x × a[x+1]；W2 的增量是 -(n-(x+1))×a[x+1]。合起来：

f(x+1) - f(x) = (2x + 1 - n) × a[x+1]

这个式子太舒服了。如果题目保证 a[i] 全部非负，那么 f(x) 的增减完全由 2x + 1 - n 的符号决定。也就是说，x 较小时 f(x) 单调下降，x 较大时单调上升，整个函数是个“碗”形，最大值只可能出现在两个端点。当然，如果 a[i] 正负都有，差分符号就不确定了，老老实实 O(n) 扫描每个位置取 max 最稳妥。

这个差分推导的价值在于：它让你真正理解 f(x) 的变化规律，而不是只会套模板。面试或者写题解的时候，能写出这一层，别人就知道你不只是背了代码，你是真的把式子吃透了。

2.3 完整 AC 代码与下标细节

代码我习惯用 1-index，因为这样跟题面里的“第 i 个元素”一一对应，不容易错。写得干净一点：

#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<long long> a(n + 1); for (int i = 1; i <= n; i++) cin >> a[i]; vector<long long> W1(n + 1, 0), W2(n + 3, 0); // 前缀加权和：W1[i] = sum_{j=1..i} (j-1) * a[j] for (int i = 1; i <= n; i++) { W1[i] = W1[i - 1] + (long long)(i - 1) * a[i]; } // 后缀加权和：W2[i] = sum_{j=i..n} (n-j) * a[j] for (int i = n; i >= 1; i--) { W2[i] = W2[i + 1] + (long long)(n - i) * a[i]; } long long ans = LLONG_MIN; // x 可以从 1 到 n-1；如果允许空段，则改成 0 到 n for (int x = 1; x <= n - 1; x++) { ans = max(ans, W1[x] + W2[x + 1]); } cout << ans << endl; return 0; }

几个下标细节值得专门说一下。W2 数组一定要多开两个空间，因为循环里会访问 W2[i+1]，i=n 时是 W2[n+1]，你需要保证这个位置存在且为 0。如果你只开到 n+1，在某些编译器下不会报错，但值是野的，答案就莫名其妙错了。这个坑我踩过不止一次。

另外 (long long)(i - 1) * a[i] 这个强制转换一定不能省。i 和 a[i] 都是 int，两个 int 相乘会先按 int 计算再赋值，一旦乘积超过 2^31-1，得到的是一个已经溢出的 int，转 long long 也救不回来。

3. 这类题的变式和进阶优化

3.1 如果系数不是 i-1 和 n-i 怎么办

好，基础版做完了，但你得清醒一点，原题基本不可能只给你这么顺滑的系数。它可能把 (i-1) 换成 (i+1)，把 (n-i) 换成 (n-i+1)，也可能在右侧乘上另一个数组 b[i]，比如右侧贡献是 (n-i)×b[i]，左侧还是跟 a[i] 有关，两侧用两种数组做双前缀维护。

思路不会变：凡是“只跟左端点有关”“只跟右端点有关”的贡献，都可以通过前缀和后缀预处理去解决。你只需要回答一个问题——当我固定分割点 x 时，每一部分的贡献能不能写成某个前缀或后缀的某种统计量？如果能，下一步永远是定义两个辅助数组，把内层循环拆掉。

有些题更阴险，它把分割点要求成“左侧至少两个元素，右侧至少一个元素”，或者“左右非空且左侧元素个数必须是偶数”。这种限制照样能处理，无非是在枚举时跳过不合法的 x，或者把前缀数组定义成只统计偶数位置。不要被这种表面限制吓住，核心的“前缀+后缀”模型一点没变。

3.2 决策单调性与分治优化

如果你遇到的变式里，f(x) 的差分不再是简单表达式，而是每一项还跟别的数组有关，导致 f(x) 不是严格的“碗形”，那 O(n) 扫描可能会失效，但你还有一种常见工具：决策单调性。

什么叫决策单调性？简单说就是，最优分割点 x 会随着某个参数（比如 n 增大）单调移动。如果题目让你对很多次不同的区间询问答案，而最优 x 满足单调性，你可以用分治优化，把原本“每次询问都扫描一遍”的复杂度降下来，总复杂度大约是 O(m log n) 到 O((n + m) log n) 级别。

判断决策单调性最靠谱的办法还是推不等式，或者直接看差分符号会不会只有一个转折点。竞赛里很多“选分界点求最大”的题，本质都是决策单调性 + 分治优化，或者再加一个李超线段树做斜率优化。这里不展开，因为篇幅有限，但你心里得有这根弦：一道题能 O(n) 扫描，不代表最优解法就止步于此，出题人完全可能在 n 和询问次数上再加大力度。

3.3 取模、溢出与 __int128 的兜底

很多题为了让答案不无限膨胀，会要求对某个大质数取模。这里有个特别容易翻车的点：如果你要找的是“真实值最大”，但最后要输出这个最大值对 mod 取余的结果，运算过程绝对不能“边取模边比大小”。

为什么？因为取模破坏了大小关系。假设真实值一个是 999 一个是 1000，mod 1000 后一个是 -1 移位，一个是 0，你比较之后选出了 0 对应的那个，但真实答案明明是 999。所以正确做法是：计算和比较时用真值，只在最终输出前取模。如果真值可能连 long long 都放不下呢？那就用 GCC 扩展类型 __int128。它最大能到约 1.7×10^38，绝大多数“看起来很大”的中间结果都能吞下。注意 __int128 不能直接 cin/cout，要自己手写输入输出，比赛环境支持度也基本没问题，但不要用到正式题解里。

我个人的习惯是：只要涉及“加权和”或“前缀乘积和”，一律先把数组开成 long long，乘法里再顺手套一个 (long long)。这是成本最低的保险，没有必要为了省几个字节去开 int。

4. 我踩过的坑：WA、TLE、对拍全记录

4.1 边界条件一改，答案就翻车

这类分割点题目，第一个隐形杀手是边界。x 能不能等于 0？能不能等于 n？如果 x=0 意味着左段为空，x=n 意味着右段为空。不同的题目设定答案完全不同。有的题目允许空段，那么你的循环要写成 x 从 0 到 n；有的题目严格要求两段都非空，那 x 只能从 1 到 n-1。一旦搞错，小样例可能侥幸通过，大数据里边界情况直接 WA。

我的做法是拿到题先死抠这一句话：“分割点”的定义里有没有说左右都至少有一个？如果没有，请手动测试 x=0 和 x=n 两个极端。另外，输出负数答案、所有数相同、n=1、n=2 这几种极端case，写题的时候务必自己先测一遍。

4.2 int 溢出：最隐蔽的锅

还有一次，我写完 O(n²) 暴力拿去对拍，暴力版用 long long，优化版也用了 long long，但样例一到 1e5 级别就开始 WA。查了半小时，最后发现是前缀数组预处理里有个地方写成了 int len = i - 1，然后 len * a[i] 两个 int 相乘，结果溢出成负数了。就这么简单且愚蠢。

认真复盘一下：只要 n 超过 1e5，a[i] 超过 1e9，加权和很容易冲到 1e14 以上，这已经超出 int 上限了。所以我的铁律是：涉及累加、累乘、下标乘值的变量，全部无脑 long long，不要在脑子里给数据“预估大小”，因为几乎所有溢出都是预估错误造成的。