企业官网建设流程全解析

1. 从题面到关键结论：f(i,j) 就是区间 lcm

这道题我刚拿到手的时候，第一反应是“又要推 lcm 的区间贡献公式”，说实话有点头疼。但仔细读完题面，发现数据范围藏在背景设定里：每个 a_i 都是 Niton 数，也就是质因子只可能是 2 和 3。这个限制直接改变了整个题的难度走向。

先把题面翻译成人话：有一个长度为 n 的数组，定义 f(i,j) 表示从区间 i~j 中选出一个非空子序列，所有选出来的数的 lcm 的最大值，然后求所有满足 i<j 的 f(i,j) 之和。

这里有个很容易踩的坑：f(i,j) 并不是“区间所有数的 lcm”，而是“所有子序列 lcm 的最大值”。初看这俩不一样，因为如果只选一部分数，lcm 可能比全选小。但本题特殊——质因子只有 2 和 3，导致所有子序列 lcm 的最大值恰好等于区间内所有数的 lcm。

为什么？设 a_k = 2^{x_k} * 3^{y_k}。任意一个子序列的 lcm，它的 2 的指数一定不超过这个区间内所有 x_k 的最大值，3 的指数一定不超过所有 y_k 的最大值。而如果我把区间里所有数都选上，这两个上界能同时达到。所以最大值就是全选，也就是区间 lcm。这个结论是整个做法的地基，虽然简单，但一定要先想清楚。

得到这个结论后，题目就变成了：求所有子区间 lcm 之和。注意题目要求 i<j，也就是长度至少为 2 的区间。后面实现时我们一般先算所有长度 ≥1 的区间，最后再减去长度为 1 的区间贡献。

2. 把 lcm 映射成二维点：max 操作是核心

既然每个数只含 2 和 3 两种质因子，那么每个数 a_i 都能唯一表示成二维坐标 (x_i, y_i)。比如 a_i = 12 = 2^2 * 3^1，对应点 (2,1)。一个区间 [l,r] 的 lcm 就对应点：

( max_{i∈[l,r]} x_i , max_{i∈[l,r]} y_i )

也就是说，区间 lcm 的质因子指数，等于区间内每个质因子指数的最大值。lcm 这个看起来很不“可加”的运算，在二维坐标下变成了逐项取 max。这是本题最核心的转化。

这时问题变成：有 n 个二维点 (x_i, y_i)，对每个子区间，求区间内点坐标的逐项最大值，然后累加 2^X * 3^Y。如果直接枚举所有区间，O(n^2) 肯定不行。但 x_i 最大是 30（因为 2^30 约 1e9），y_i 最大是 18（因为 3^18 约 3.8e8），坐标范围特别小，这个性质要好好利用。

我一开始想偏了，试图对每个数单独算贡献，比如统计每个 (x,y) 出现多少次，然后乘上某个权重。测样例发现不对，原因是区间 [2,3] 的 lcm 是 6 = 2^1 * 3^1，而这个点 (1,1) 不属于原数组中的任何一个数。也就是说，区间 lcm 的二维坐标可能是多个数“互补”出来的，不能简单按原始点做贡献拆分。这个坑希望大家不要再踩。

3. 从左端点的角度看：状态段数为什么有界

现在考虑一个固定右端点 r。对于每个左端点 l，设 S_l = (X_l, Y_l) 是区间 [l,r] 的 lcm 坐标。当 l 从 1 增大到 r 时，区间越来越短，所以 X_l 单调不增，Y_l 也单调不增。也就是说，序列 S_1, S_2, ..., S_r 是一个二维单调不增序列。

如果我们把连续相同的 S_l 合并成一段，那么相邻两段的坐标至少有一个严格变小。因为 X 最多从 30 降到 0，Y 最多从 18 降到 0，所以两坐标的总变化次数最多 30+18=48 次，因此段数最多 49 段。这个上界非常重要，是整个算法复杂度的保证。

举个例子帮助理解：假设固定 r，左端点 l 从 r 往左移动，每加入一个新数，X 和 Y 只会变大或不变。一次“变大”至少消耗 1 的指数增量，而 X 总共只能增加 30 次，Y 总共只能增加 18 次，所以变化次数有限。这不是玄学，而是坐标范围给的福利。

因此，我们可以枚举右端点 r，同时维护一个压缩后的状态数组，里面存若干段连续的左端点区间，每段有相同的 (X,Y)。每次加入新右端点时，所有旧段的 (X,Y) 都要和新点的 (x_r, y_r) 取 max，然后新增一段长度为 1 的区间，再把相邻相同段合并。由于段数最多 49 段，整体复杂度 O(n * 49)，非常稳。

4. 全量更新 + 合并：我的实现思路与代码

代码实现我推荐一种最直观的写法：不搞复杂的栈内合并顺序，直接“全量更新旧段，末尾追加新段，再合并相邻相同段”。段数很小，所以全量更新完全可行，逻辑也最不容易错。

具体流程如下：

预处理每个 a_i 的 (x_i, y_i)，即分解出 2 的指数和 3 的指数。可以用 while 循环不断除以 2 和 3。

枚举右端点 r 从 1 到 n：

1. 取出当前点 (curx, cury)。
2. 遍历当前所有旧段，把每段的 (X,Y) 更新为 (max(X, curx), max(Y, cury))。
3. 在末尾追加一个新段 (curx, cury, cnt=1)，表示左端点等于 r 的长度为 1 的区间。
4. 从左到右扫描所有段，如果相邻两段的 (X,Y) 完全相同，则合并成一个段，cnt 相加。
5. 遍历最终所有段，累计答案：每段贡献 cnt * 2^X * 3^Y。

这里有个细节要注意：步骤 2 中所有旧段与新点取 max 后，仍然保持从左到右单调不增的性质，因为“和固定点取 max”不会破坏单调性。追加的新段在最右端，它的坐标一定小于等于左边所有段的坐标，因为区间 [r,r] 是当前右端点下最短的区间，它的 max 不可能超过包含它的更长区间。所以合并逻辑没问题。

我用了 powers 预处理 2^X 和 3^Y，X 最大 30，Y 最大 18，所以数组开到 35 和 25 足够。每段 cnt 最大是 n，用 long long 更安全。累加答案时每步取模，避免溢出。

下面给一份完整的 C++ 代码，我比赛时基本是按这个思路写的：

#include <bits/stdc++.h> using namespace std; using ll = long long; const ll MOD = 1000000007; // 请根据题目实际模数修改 struct Seg { int x, y; ll cnt; }; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> a(n + 1); for (int i = 1; i <= n; i++) cin >> a[i]; vector<ll> pow2(35, 1), pow3(25, 1); for (int i = 1; i < 35; i++) pow2[i] = pow2[i - 1] * 2 % MOD; for (int i = 1; i < 25; i++) pow3[i] = pow3[i - 1] * 3 % MOD; vector<pair<int, int>> pts(n + 1); ll single_sum = 0; for (int i = 1; i <= n; i++) { int x = 0, y = 0, t = a[i]; while (t % 2 == 0) { x++; t /= 2; } while (t % 3 == 0) { y++; t /= 3; } pts[i] = {x, y}; single_sum = (single_sum + pow2[x] * pow3[y]) % MOD; } vector<Seg> seg; ll ans = 0; for (int r = 1; r <= n; r++) { int curx = pts[r].first, cury = pts[r].second; for (auto &s : seg) { s.x = max(s.x, curx); s.y = max(s.y, cury); } seg.push_back({curx, cury, 1}); vector<Seg> merged; for (auto &s : seg) { if (!merged.empty() && merged.back().x == s.x && merged.back().y == s.y) { merged.back().cnt += s.cnt; } else { merged.push_back(s); } } seg = move(merged); for (auto &s : seg) { ans = (ans + s.cnt % MOD * pow2[s.x] % MOD * pow3[s.y]) % MOD; } } ans = (ans - single_sum + MOD) % MOD; cout << ans << "\n"; return 0; }

验证一下样例：n=2，a=[2,3]。预处理得到点 (1,0) 和 (0,1)，single_sum = 2 + 3 = 5。

r=1，cur=(1,0)，旧段为空，追加新段 (1,0,1)，合并后只有一段，累加 ans = 2^1 * 3^0 = 2。这个 2 对应区间 [1,1]。

r=2，cur=(0,1)，旧段 (1,0) 更新为 (1,1)，追加新段 (0,1,1)，合并后两段不相等，所以段序列是 [(1,1,1), (0,1,1)]。累加：1 * 2^1 * 3^1 = 6，加上 1 * 2^0 * 3^1 = 3，ans 变成 11。对应区间 [1,1]=2，[1,2]=6，[2,2]=3。最后 ans - single_sum = 11 - 5 = 6，正是 f(1,2) = lcm(2,3) = 6。完全正确。

5. 题目要求的 i<j：为什么最后减单点贡献最稳

题目求的是 sum_{i=1}^n sum_{j=i+1}^n f(i,j)，也就是只统计长度至少为 2 的区间。上面的代码先算了所有 i≤j 的区间总和，然后减去了所有长度为 1 的区间贡献，即每个位置的 a_i 本身。

这里我提醒一个容易写错的点：不要试图在遍历段时“跳过”新追加的那一段，因为新段很可能在合并时和前面的段合到一起，从而无法分辨哪个左端点对应 l=r。所以最简单可靠的方式就是最后统一减掉 Σ a_i。

另外，减完后要加 MOD 再取模，避免负数答案。这个虽然是小细节，但真有人因此 WA 过。

还有一点是关于 lcm 最大值和子序列的问题。原题说的是“选出非空子序列”，由于没有限制子序列长度，所以全选区间一定可行，且一定是最大。如果某天题目改成“必须选两个不同的数”或“子序列长度恰好为 k”，那这个结论就要重新考虑了。读题时一定看清楚。

6. 为什么不能直接按数贡献：一个必须理解的失败尝试

我一开始把问题想简单了：每个数 a_i 是 2^{x_i} * 3^{y_i}，是不是统计所有区间时，只要对每个位置算它对哪些区间的 lcm 有贡献就行了？比如经典的“统计区间 gcd”问题就可以对每个位置维护 gcd 变化段。但 gcd 和 lcm 有本质区别：gcd 的值随区间扩大而单调不增，lcm 的值随区间扩大而单调不减。对于 gcd，每个位置作为“新加入元素”时，它能改变的状态段数可以用 O(log V) 控制。对于 lcm，如果数组里的数包含很多不同质因子，每次加入一个新素数都会让 lcm 变化一次，线段数可能达到 O(n)。

本题之所以能做，是因为质因子只有 2 和 3，二维状态空间极小。如果还是试图单独统计每个数对区间的“新增贡献”，会遇到一个麻烦：一个区间的 lcm 可能由多个数组合而成，比如 2 和 3 合出 6，而 6 这个值不属于任何一个单一原始数。所以你在按 x 贡献或者按 y 贡献时，无法直接拆分。

从二维点视角看，这个问题就很清晰：区间 [l,r] 的贡献是 2^{max x} * 3^{max y}，这是一个关于 max 的乘积函数，不是可加的。所以必须维护所有可能 (X,Y) 的组合状态，而不是单个数的贡献。

这里我还想多提一句：2^X * 3^Y 看起来像两个独立维度的乘积，但我们不能把两个维度的贡献拆开分别算，比如“所有区间最大 x 的 2 次幂之和”和“所有区间最大 y 的 3 次幂之和”相乘——因为每个区间的最大 x 和最大 y 是同一个区间的两个属性，不能解耦。代码里把 (X,Y) 作为一个整体存入段中，正是因为这个原因。

7. 比赛时的调试心得：如何快速验证正确性

这类题写完代码后，我建议先自己构造几组小数据手算，再和程序输出对比。这里分享几个我常用的测试用例。

第一组是 n=1，只有一个数。此时没有任何 i<j 的区间，答案应该是 0。我们的代码会先算出区间 [1,1] 的贡献 a_1，再在最后减去 single_sum = a_1，得到 0。这个测试能检查减单点逻辑。

第二组是 n=2，a=[1,1]。两个数都是 1，那么 f(1,2) = lcm(1,1) = 1，答案应该是 1。代码里点坐标都是 (0,0)，r=1 累加 1，r=2 更新后段 (0,0,cnt=2)，累加 2，总数 3，减去 single_sum=2，得到 1。

第三组是 n=3，a=[2,3,4]。2 对应 (1,0)，3 对应 (0,1)，4 对应 (2,0)。手动算一下所有长度≥2区间的 lcm：区间 [1,2]=6，[1,3]=12，[2,3]=12，总和 30。程序输出应该也是 30。我建议读者在本地跑一下这组数据，如果结果不对，基本可以确定是合并逻辑或取模问题。

另外，如果害怕段数上界理解错了，可以在代码里加一个统计最大段数的变量，跑完随机数据看看是否超过 49。我实测随机生成 2e5 个点，最大段数一般只有 8 到 12 左右，49 这个上界是非常宽松的。这也说明即使某个角度上数据稍微放宽一点，比如 y 指数上限变成 20，算法依然没问题。

8. 如果质因子不止 2 和 3：这个做法还能推广吗

我在赛后想了想，如果 a_i 的质因子集合变成 {2,3,5}，这个做法还能用吗？答案是：只要质因子种类数还是常数且每个质因子的指数上界都较小，就可以继续用同样的思路。

把每个数映射成三维向量 (x,y,z)，区间 lcm 变成逐维取 max，状态段数上界就变成三个指数上界之和，大概是 30+18+12≈60 段，依然很小。所以代码框架几乎不用改，只是每个点的维度增多，合并时要比较三个坐标，贡献变成 2^X * 3^Y * 5^Z。

但如果质因子种类很多，比如有 20 个不同质因子，状态维度变成 20 维，段数上界会很大，这个“全量更新所有段”的做法就不可行了。这时候往往需要更复杂的数据结构，比如线段树维护 max 矩阵、分治离线，或者题目本身 n 会限制得很小。总之，这类题第一步永远是数质因子数量，再决定算法路线。

我这里给一个可能有点用的经验：比赛时看到 lcm 区间求和，不要先想高级数据结构，而是先看值域和质因子限制。如果每个数都能被很少的质因子表示，那么 lcm 的变化状态一定不多。本题就是最典型的例子。

9. 最终代码需要注意的几个边界细节

最后集中说几个写代码时容易出问题的点，都是我实际踩过的。

第一个是预处理指数时的循环。如果 a_i = 1，那么 x=0，y=0，两个 while 都不会进入。这种情况是合法的，不要漏掉。模数比较大时，pow2[0] * pow3[0] = 1，贡献为 1，单点贡献也要算进去。

第二个是合并段时用一个新 vector 重新构造，不要在原 vector 上一边遍历一边删。因为遍历时下标会乱掉，而且合并后需要更新 back，原地操作容易写错。我上面的代码先用 merged 收集再 swap，简单可靠。如果你熟悉双指针也可以，但没必要。

第三个是答案取模的位置。cnt 最多 2e5，pow2[s.x] 和 pow3[s.y] 都是模数范围内的数，但乘起来可能超过 long long？其实 2e5 * 1e9 * 1e9 = 2e23，远超 long long，所以必须在乘法过程中逐次取模。代码里写成 s.cnt % MOD * pow2[s.x] % MOD * pow3[s.y]，每次乘完都取模，这样安全。

第四个是最后 ans - single_sum 后要加 MOD 再取模。因为 ans 和 single_sum 都是在模意义下的，直接相减可能是负数。加上 MOD 只会修正一次，因为两者都在 [0, MOD) 区间，相减后最小是 -(MOD-1)，加一次 MOD 足够。

第五个是输入量可能比较大，用 ios::sync_with_stdio(false) 和 cin.tie(0) 加速。虽然 n=2e5 不大，但养成习惯没坏处。

我把这些细节写这么细，是因为比赛时我就曾经因为“先减单点再取模”导致负数输出，又因为“乘法顺序不对”导致溢出。最关键的是，我一开始错误理解了子序列 lcm 的最大值，以为需要排除某些数，结果完全跑偏。希望大家看了这篇后不要再走这些弯路。

10. 我对这道题的整体评价与实操建议

TBOI Round 1 的这道 P15409，放在赛题里属于“思路巧妙但不难写”的类型。它的难点不在代码量，而在两个思维跳跃：

第一个跳跃是从“子序列 lcm 最大值”意识到等于“区间 lcm”。这个跳跃依赖对质因子分解后取 max 的深刻理解。第二个跳跃是意识到“所有左端点对应的二维状态段数有界”，从而可以用压缩状态暴力扫。

如果让我给一个建议，就是做题时多注意数据范围里的“隐藏限制”。这题的 a_i ≤ 1e9 看起来很普通，但题面明确指出只有 2 和 3 两种质因子。类似的陷阱在不少比赛里都出现过：数字很大，但质因子种类极少，或者所有数都是某个数的幂，这些都能把 lcm / gcd 类问题的状态空间压到很小。

从代码结构来说，这份题解用的“全量更新旧段 + 末尾追加 + 合并相邻段”是我认为最适合比赛速写的写法。它不像一些题解里写的那种“从栈顶向前合并”需要仔细维护顺序关系，也不容易在合并时丢状态。虽然每个右端点要遍历全部段更新，但段数 max 只有 49，实测常数可以忽略不计。

最后分享一个小技巧：任何时候你觉得一个算法要套很重的东西，先花几分钟想想状态总数到底有多少。如果状态总数不超过几百或几千，那大概率有暴力压缩的办法。这题就是最好的例子。希望这篇题解能帮你彻底搞懂 P15409，也能让你在面对其他 lcm 区间求和问题时多一条思路。