例 1：所有子段和之和（最简单）#

题目：给定数组 a[1..n]，求 $\sum_{l=1}^n \sum_{r=l}^n \text{sum}(a[l..r])$

枚举视角：O(n³) 或前缀和压到 O(n²)

贡献视角：每个元素 a[i] 在多少子段中出现？

1
ans = 0
2
for i in range(1, n+1):
3
    ans += a[i] * i * (n - i + 1)

O(n)，一行。

例 2：所有子段最大值之和（单调栈 + 贡献法）#

题目：求所有子段的最大值之和。

贡献视角：a[i] 在多少子段里是最大值？

单调栈预处理：找到左边第一个大于 a[i] 的位置 L，右边第一个大于 a[i] 的位置 R。

在 (L, R) 区间内，a[i] 是唯一最大值。子段要满足 a[i] 是最大值：

1
# 单调栈预处理 L[i] 和 R[i]
2
for i in range(1, n+1):
3
    ans += a[i] * (i - L[i]) * (R[i] - i)

例 3：史莱姆困难版（载体是匹配关系）#

题目：所有连续子段源数之和。

简单版回顾：从右往左栈，v → v+1 匹配，栈大小 = f(l,r)

困难版核心观察：全局匹配边 (i → j) 在任何包含 i 和 j 的子段中都保持有效。

• 子段包含 [i, j] 时：匹配边生效，减少一次源数（少一个初始史莱姆）
• 子段不包含 i 或 j 时：匹配边失效

贡献法：载体不是元素，是匹配边本身。

每条全局匹配边 (i → j) 被多少子段包含？

最终公式：

1
total = n * (n + 1) * (n + 2) // 6
2
stack = []
3
for i in range(n-1, -1, -1):
4
    while stack and a[stack[-1]] == a[i] + 1:
5
        j = stack.pop()
6
        total -= (i + 1) * (n - j)
7
    stack.append(i)

卡住的真正原因#

不是智商问题，是思维习惯：

1. 遇到「所有子段」，第一反应永远是枚举子段——这是本能的、正常的
2. 发现枚举会炸后，试图用分治/线段树/双指针「优化枚举」——仍然是枚举视角
3. 没有立刻回头找结构不变量（全局匹配边在子段中不变的属性）

改进方向#

• 遇到「所有 X 之和」，强制先问：能不能选载体？能不能交换求和顺序？
• 发现枚举炸了，不要继续优化枚举，立刻回头找不变量
• 刷 5~10 道贡献法专题题，让这个思维成为肌肉记忆

和维什戴尔题的呼应#

维什戴尔火力覆盖题花了 4 小时才 AC，同样是因为「枚举所有部署 + 所有怪物」的思维惯性。那题虽然没有显式用贡献法，但同样需要反向建图——枚举每只怪物能被哪些部署覆盖，而不是枚举每个部署能覆盖多少怪物。

方向反转是 ACM 中高阶题的核心思维模式，贡献法是其中最重要的具体技法之一。