Skip to content

贡献法

不枚举每个区间,改成统计每个元素被算了几次。

Updated View as Markdown

有一类题目的字面要求是「所有子区间的某种量加起来是多少」。按字面去做,枚举所有区间是 O(n^2),n 到 10^5 就超时了。贡献法换个角度数数,往往能把复杂度降一个量级。

本章的知识点与 GESP、CSP-J/S 大纲的对应关系如下。

考试 大纲要求 本章位置
CSP-J/S 第一轮 换个角度统计的思想常出现在阅读程序与完善程序中 全章
GESP C++ 八级 考点 8:算法优化,理解不同方法在时空复杂度上的差异 全章
CSP-J/S 入门级 2.4 基本运算:位运算(按位拆开统计) 例二、例四、例五、练习 2/5/6/7
CSP-J/S 提高级 4.4 算法策略:单调栈配合贡献法(子数组最值之和) 例三、练习 3

核心思路

正向统计是:对每个区间,把区间里所有元素的贡献加起来。

贡献法是:对每个元素,统计它在多少个区间里被算到,乘上它自己的值。

\text{答案} = \sum_{\text{每个元素}} (\text{元素的值} \times \text{它被统计到的次数})

关键问题从「有多少个区间」变成了「这个元素出现在哪些区间里」。后者往往能用左边界和右边界的组合数快速算出来。

例一:所有子数组的元素和之和

给定数组,求所有连续子数组的和再全部加起来的和。

朴素做法要枚举左右端点,O(n^2)。换成贡献法看元素 a[i](下标从 1 开始):

  • 一个子数组包含 a[i],当且仅当左端点在 1 到 i 之间,右端点在 i 到 n 之间。
  • 左端点有 i 种选法,右端点有 n - i + 1 种。
  • 所以 a[i] 被 i \times (n - i + 1) 个子数组包含。

\text{答案} = \sum_{i=1}^{n} a[i] \times i \times (n - i + 1)

long long ans = 0;
for (int i = 1; i <= n; i++) {
    ans += 1LL * a[i] * i * (n - i + 1);
}
cout << ans << endl;

一次循环就够了,O(n)。注意这里乘出来可能超过 int,所以要用 1LL 把运算提升到 long long。

例二:按位统计

求所有子数组按位或的和,或者按位与的和。这类题不能整体统计,但可以按二进制位分别算。

以按位或为例。对第 b 位,我们想知道有多少个子数组的或值在这一位上是 1。正面算不好算,就算反面:这一位全是 0 的子数组有多少个。

把数组中第 b 位为 0 的位置连成一段段连续区间,每一段长度为 len 的全零段能贡献 len \times (len + 1) / 2 个全零子数组。总数减去全零的,就是这一位为 1 的子数组个数,乘上 2^b 累加到答案里。

long long ans = 0;
for (int b = 0; b < 31; b++) {
    long long zero = 0;      // 这一位全为 0 的子数组数
    long long len = 0;       // 当前连续的全零段长度
    for (int i = 1; i <= n; i++) {
        if ((a[i] >> b) & 1) {
            zero += len * (len + 1) / 2; // 结算这一段
            len = 0;
        } else {
            len++;
        }
    }
    zero += len * (len + 1) / 2;
    long long total = 1LL * n * (n + 1) / 2; // 子数组总数
    ans += (total - zero) * (1LL << b);
}
cout << ans << endl;

按位处理是位运算题的通用套路:整体难算的,拆成 31 位,每一位单独统计再合并。

上面假设所有数都是非负整数且小于 2^{31}(int 的范围)。如果题目里出现了负数或者更大的数,位数的上界要相应调整。

例三:每个数作为最大值的区间数

求所有子数组的最大值之和。对每个 a[i],算出「以 a[i] 为最大值的子数组」有多少个,再乘上 a[i]。

设左边第一个严格大于 a[i] 的位置是 L,右边第一个大于等于 a[i] 的位置是 R(一边严格、一边非严格,是为了避免相同的数被重复统计)。那么左端点可以在 L+1 到 i 之间,右端点在 i 到 R-1 之间:

\text{个数} = (i - L) \times (R - i)

L 和 R 可以用单调栈在 O(n) 内全部求出。这正是《栈与队列》里单调栈的经典用法。

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;
long long a[N];
int L[N], R[N];

int main() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];

  // L[i]:左边第一个「严格大于」a[i] 的位置,没有则记 0
  stack<int> st;
  for (int i = 1; i <= n; i++) {
    while (!st.empty() && a[st.top()] <= a[i]) st.pop();
    L[i] = st.empty() ? 0 : st.top();
    st.push(i);
  }

  // R[i]:右边第一个「大于等于」a[i] 的位置,没有则记 n+1
  while (!st.empty()) st.pop();
  for (int i = n; i >= 1; i--) {
    while (!st.empty() && a[st.top()] < a[i]) st.pop();
    R[i] = st.empty() ? n + 1 : st.top();
    st.push(i);
  }

  long long ans = 0;
  for (int i = 1; i <= n; i++) {
    ans += a[i] * 1LL * (i - L[i]) * (R[i] - i); // 以 a[i] 为最大值的子数组个数
  }
  cout << ans << endl;
  return 0;
}

注意两边的判断条件不一样:左边的栈弹出条件是 <=,右边是 <。一边严格、一边非严格,相同的数才不会在两个位置上各被统计一次。

例四:所有数对的按位与之和

求所有数对 (i, j)(i < j)的按位与之和。

这题和「异或和」是同一套框架,区别只在「什么样的数对能让这一位变成 1」:

运算 第 b 位结果为 1 的条件 贡献
异或 两个数这一位不同 c_1 \times c_0
与 两个数这一位都是 1 c_1 \times (c_1 - 1) / 2
或(数对) 两个数这一位至少一个为 1 \dfrac{n(n-1)}{2} - \dfrac{c_0(c_0-1)}{2}

其中 c_1 是这一位为 1 的数的个数,c_0 = n - c_1。

long long ans = 0;
for (int b = 0; b < 20; b++) {
    long long c1 = 0;
    for (int i = 0; i < n; i++) c1 += (a[i] >> b) & 1;
    ans += c1 * (c1 - 1) / 2 * (1LL << b); // 从 c1 个里任取两个
}

这张表值得背下来:三种位运算的数对/子数组统计,都是「按位拆 + 数清这一位为 1 的个数 + 算出方案数」。

例五:子数组的按位与之和

求所有连续子数组按位与之和。注意这已经不是数对问题了,而是子数组问题。

按位看第 b 位:一个子数组的与在这一位为 1,当且仅当这个子数组里所有数在这一位都是 1。

所以做法和例二(按位或)正好相反:

  • 例二(或):把为 0 的位置切成段,数「全零子数组」的个数,再用总数减去;
  • 例五(与):把为 1 的位置切成段,数「全一子数组」的个数,直接累加。
long long ans = 0;
for (int b = 0; b < 20; b++) {
    long long one = 0, len = 0;
    for (int i = 1; i <= n; i++) {
        if ((a[i] >> b) & 1) {
            len++;              // 这一位是 1,段长加一
        } else {
            one += len * (len + 1) / 2; // 段结束,结算这一段的全一子数组
            len = 0;
        }
    }
    one += len * (len + 1) / 2;
    ans += one * (1LL << b);   // 全一子数组的个数 × 这一位的权重
}

一个长度为 len 的「全 1 段」里,任意选左右端点都得到一个全一子数组,共 len(len+1)/2 个。

把例二和例五对着读一遍,能看出一个很好用的思维定式:「或」统计 1 的补集(全 0 段),「与」统计 1 本身(全 1 段)。因为「或为 1」只要有一个 1,不好直接数;而「与为 1」要求全是 1,正好是连续的 1。

什么时候想到贡献法

  • 题目要求「所有子区间的某种量之和」,按区间枚举是 O(n^2) 及以上。
  • 每个元素的「影响」可以用它左右两侧的位置范围描述。
  • 涉及位运算,可以按位拆开统计(数对型和子数组型的公式不同)。
  • 要求「所有子数组的最大值/最小值之和」,用单调栈求出每个元素作为最值的边界。

复杂度对比

做法 复杂度
枚举左右端点 O(n^2),位运算题还要再乘位数
贡献法 O(n),或 O(n \log n)(需要排序、单调栈)

常见易错点

  • 相乘时忘记开 long long。n = 10^5 时 i \times (n-i+1) 最大约 2.5 \times 10^9,已经超过 int。
  • 统计「包含某元素的区间数」时,左右端点的可行范围容易数错一位,画个图示最稳。
  • 处理相同的数时,单调栈一定要做到「一边严格、一边非严格」,否则重复计数。
  • 贡献法是「换角度」,不是「省略计算」。答案算错的常见原因是贡献次数推错,而不是代码写错。
  • 混用「数对」与「子数组」的公式。数对是 \binom{c_1}{2},子数组是 \sum\frac{len(len+1)}{2},两者不能互相套用。
  • 分段统计漏掉最后一段。循环结束后 len 里可能还存着一段没结算的连续区间,必须再补一次。
  • c1*(c1-1)/2 或 len*(len+1)/2 用 int。10^5 量级相乘就到 10^{10},必须提升到 long long(写成 1LL * ... 或先把变量声明成 long long)。

练习

下面的练习都已经收录进题库,点击每道题的「在线评测练习」可以直接提交评测;题面与数据范围以题库为准,课堂上的分析和代码则只围绕本章的「贡献法」展开,方便对照前面的核心思路直接套用。

练习 1:所有子数组的和之和

在线评测练习:P1517 所有子数组的和之和

题目描述

给定 n 个整数,求它所有连续子数组的元素和之和。

输入格式

第一行一个整数 n。

第二行 n 个整数,相邻两个整数之间用一个空格隔开。

输出格式

输出一个整数,表示所有连续子数组元素和的总和。

数据范围

  • 1 \le n \le 10^5。
  • |a_i| \le 10^4。

输入输出样例

输入

3
1 2 3

输出

20

六个子数组分别是 [1]、[2]、[3]、[1,2]、[2,3]、[1,2,3],和分别是 1、2、3、3、5、6,加起来是 20。

输入

3
-1 -2 -3

输出

-20

全是负数时答案为负,不能初始化为 0。

题目分析

把本章例一写成标准输入输出,是贡献法最干净的入门:不枚举区间,改成问「每个元素被多少个区间算到」。

下标从 1 开始,a_i 被包含,当且仅当左端点落在 1 \sim i、右端点落在 i \sim n。左端点 i 种选法、右端点 n - i + 1 种,所以

\text{答案} = \sum_{i=1}^{n} a_i \times i \times (n - i + 1)

一遍循环,O(n)。对比枚举左右端点的 O(n^2),这就是本章开头说的「降一个量级」。

两个必须注意的点:

  • 乘积要用 long long。 n = 10^5 时 i \times (n - i + 1) 最大约 2.5 \times 10^9,已经越过 int 上限(约 2.1 \times 10^9)。代码里写 x * 1LL * i * (n - i + 1),把 1LL 放在最前面让整条表达式提升到 64 位——这是本章易错点第一条。
  • ans 要允许负数。 第二个样例全是负数,答案 -20。贡献次数恒为正,符号完全来自 a_i 本身,所以初值写 0 是对的,但绝不能因为「看起来像求和」就把它当成非负的量去用无符号类型。

还有一个容易忽略的点:这题不需要前缀和。看到「子数组求和」很多人第一反应是预处理前缀和,但前缀和优化的是「多次询问区间和」,而本题一次也不询问——直接数贡献次数就够了。用前缀和反而是 O(n^2)(枚举所有区间再 O(1) 查询),仍然超时。

参考代码

练习 2:所有数对的异或和之和

在线评测练习:P1518 所有数对的异或和之和

题目描述

给定 n 个非负整数,求所有满足 i < j 的数对 (i, j) 的异或值 a_i \oplus a_j 之和。

输入格式

第一行一个整数 n。

第二行 n 个非负整数,相邻两个整数之间用一个空格隔开。

输出格式

输出一个整数,表示所有数对异或值的总和。

数据范围

  • 1 \le n \le 10^5。
  • 0 \le a_i < 2^{20}。

输入输出样例

输入

3
1 2 3

输出

6

三个数对:1 \oplus 2 = 3、1 \oplus 3 = 2、2 \oplus 3 = 1,加起来是 6。

输入

2
0 0

输出

0

题目分析

数对有 O(n^2) 个,直接枚举就超时。破局点是本章例二、例四讲的那条通用套路:按位拆开,每一位独立统计。

异或的性质正好适合拆位:第 b 位的结果只取决于两个数在这一位是否相同,与其它位无关。所以

\text{答案} = \sum_{b=0}^{19} 2^b \times (\text{第 } b \text{ 位为 1 的数对个数})

设第 b 位为 1 的数有 c_1 个、为 0 的有 c_0 = n - c_1 个。要让异或在这一位为 1,必须「一 1 一 0」,方案数就是

c_1 \times c_0

这就是贡献法的第二次换角度:从「枚举数对」换成「数清这一位的 0 和 1」——不再关心具体是哪两个数,只关心它们的个数。

细节:

  • 上界是 20 位。 题目保证 a_i < 2^{20},所以第 0 位到第 19 位遍历即可。本章例二写的 b < 31 是针对 int 全范围,这里按题目给的范围收窄更严谨。多写几位不会错(贡献为 0),少写就会漏答案。
  • 1LL << b 而不是 1 << b。 b = 19 时 1 \ll 19 还在 int 内,但和前面的计数相乘就溢出了,所以移位字面量也要用 64 位。
  • 答案量级。 最大约 \frac{n(n-1)}{2} \times 2^{20} \approx 5 \times 10^{15},long long 才装得下。

参考代码

练习 3:所有子数组的最大值之和

在线评测练习:P1520 所有子数组的最大值之和

题目描述

给定 n 个整数,求它所有连续子数组的最大值之和。

输入格式

第一行一个整数 n。

第二行 n 个整数,相邻两个整数之间用一个空格隔开。

输出格式

输出一个整数,表示所有连续子数组最大值的总和。

数据范围

  • 1 \le n \le 10^5。
  • |a_i| \le 10^6。

输入输出样例

输入

4
3 1 2 4

输出

30

n=4 时子数组共 4 \times 5 / 2 = 10 个,它们的最大值分别是:[3]=3、[1]=1、[2]=2、[4]=4、[3,1]=3、[1,2]=2、[2,4]=4、[3,1,2]=3、[1,2,4]=4、[3,1,2,4]=4,加起来是 30。

输入

3
5 5 5

输出

30

有重复值时也要正确计数:每个子数组的最大值都是 5,n=3 时子数组共 3 \times 4 / 2 = 6 个,总和 30。

题目分析

这道题不能像练习 1 那样「每个元素乘固定次数」——a_i 到底被算了几次,取决于它是不是所在区间里的最大值,而这和它左右两侧有没有更大的数相关。

贡献法的正确问法是:「以 a_i 为最大值」的子数组有多少个? 答案乘上 a_i 再累加。

设 L 是 i 左边第一个严格大于 a_i 的位置,R 是 i 右边第一个大于等于 a_i 的位置。那么左端点可以在 L+1 \sim i 里选、右端点可以在 i \sim R-1 里选,个数就是

(i - L) \times (R - i)

L、R 用单调栈在 O(n) 内全部求出——这正是本章小结里「要求每个元素作为最大值的区间数,用单调栈求左右边界」那条。

为什么两边一个严格、一个非严格? 这是本章易错点里专门列的一条。假设数组是 5 5:如果两边都用「严格大于」作界,那么对第 1 个 5,右边没有严格大于它的,R = 3,它被算在 [5]、[5,5] 两个区间里;对第 2 个 5,L = 0、R = 3,它也被算在 [5]、[5,5] 两个区间里。同一个区间 [5,5] 被两个位置各认领一次,最大值之和就多算了一遍。

把右边改成「大于等于」作界,第 1 个 5 的 R 就变成 2(第 2 个 5 是「大于等于」它的),它只管 [5];第 2 个 5 管 [5,5] 和它自己。每个子数组恰好被认领一次。

第二个样例 5 5 5 就是专门检查这一点的:正确总和 30(6 个子数组最大值都是 5)。如果两边都用严格,会算出 45。

细节:

  • L[i] 没有更大值时记 0,R[i] 没有更大值时记 n+1,这样 i - L[i] 和 R[i] - i 直接就是合法个数,不需要特判。
  • 单调栈的实现里,求 L 是从左往右扫、栈内递减;求 R 是从右往左扫、栈内递增。两次扫描之间要清空栈。
  • a[i] * 1LL * (i - L[i]) * (R[i] - i) 要用 long long:|a_i| \le 10^6、区间数最多约 2.5 \times 10^9,乘积到 10^{15} 量级。

参考代码

练习 4:所有数对的距离之和

在线评测练习:P1516 所有数对的距离之和

题目描述

给定 n 个整数,求所有满足 i < j 的数对的 |a_i - a_j| 之和。

输入格式

第一行一个整数 n。

第二行 n 个整数,相邻两个整数之间用一个空格隔开。

输出格式

输出一个整数,表示所有数对差的绝对值之和。

数据范围

  • 1 \le n \le 10^5。
  • |a_i| \le 10^6。

输入输出样例

输入

4
1 3 2 4

输出

10

数对之差分别是 2、1、3、1、2、1,加起来是 10。

输入

2
-1000000 1000000

输出

2000000

题目分析

绝对值破坏了「按位拆」这条路(绝对值不是位运算),但贡献法仍然好用——只要先排序把绝对值拆掉。

排好序之后 a_0 \le a_1 \le \cdots \le a_{n-1},于是对任意 i < j 都有 |a_i - a_j| = a_j - a_i,绝对值自然消失。

现在用贡献法:a_i 会出现在哪些数对的差里,各自是加还是减?

  • 它比前面的 i 个数都大,所以在这些数对里它是被减数,贡献 +a_i,共 i 次;
  • 它比后面的 n-1-i 个数都小,所以在这些数对里它是减数,贡献 -a_i,共 n-1-i 次。

合并起来,a_i 的净贡献是

a_i \times \bigl(i - (n - 1 - i)\bigr) = a_i \times (2i - n + 1)

累加即可。排序 O(n \log n) 主导复杂度。

这条是本章小结里的那句「数对型问题(异或和、差的绝对值和)也可以用贡献法,常常先排序或按位拆」的具体落地:两道数对题走了两条不同的路——异或和按位拆,绝对差先排序。

细节:

  • 排序之后原来的下标顺序就没了,所以必须先读完整份数据再排序。本题不要求按下标输出,所以没有影响;如果题目还要原始的 i < j 关系,那就不能这么排(不过差的绝对值本身与下标无关,所以安全)。
  • 系数可能为负,2i - n + 1 在 i 较小的时候是负数。这正是它表达「作减数的次数多于作被减数」的方式,不要去 abs 它。
  • 2LL * i 而不是 2 * i:i 到 10^5 时 2i 还不溢出,但和 a[i] 相乘前必须确保整体是 64 位运算。

参考代码

练习 5:所有数对的按位与之和

在线评测练习:P1514 所有数对的按位与之和

题目描述

给定 n 个非负整数,求所有满足 i < j 的数对的按位与之和。

输入格式

第一行一个整数 n。

第二行 n 个非负整数,相邻两个整数之间用一个空格隔开。

输出格式

输出一个整数,表示所有数对按位与的总和。

数据范围

  • 1 \le n \le 10^5。
  • 0 \le a_i < 2^{20}。

输入输出样例

输入

3
1 2 3

输出

3

1 \mathbin{\&} 2 = 0、1 \mathbin{\&} 3 = 1、2 \mathbin{\&} 3 = 2,加起来是 3。

输入

3
0 0 0

输出

0

题目分析

和练习 2 同一套框架——按位拆、数清这一位的 1、算方案数——区别只在「什么样的数对能让这一位变成 1」。

运算 第 b 位结果为 1 的条件 方案数
异或 两个数这一位不同 c_1 \times c_0
与 两个数这一位都是 1 \dbinom{c_1}{2} = \dfrac{c_1(c_1-1)}{2}

「与」要求两个数都是 1,所以是从 c_1 个里任取两个,即 \binom{c_1}{2}。这就是复习里那张表在本章的第一次落地,和练习 2 对着记,两题的代码结构完全一样,只有一行公式不同。

细节:

  • c1 * (c1 - 1) / 2 必须 long long。 c_1 到 10^5 时乘积到 10^{10},int 早就溢出。因为 c1 已声明为 long long,这里自然安全。
  • 先乘后除。 写成 c1 * (c1 - 1) / 2 是对的(c_1(c_1-1) 一定是偶数,且中间值在 64 位内);写成 c1 / 2 * (c1 - 1) 也可以,但 /2 放在前面时要小心 c_1 为奇数时整除的语义——虽然结果相同,可读性不如前者。
  • c_1 < 2 时自然为 0,不需要特判。第二个样例全是 0,每一位 c_1 = 0,答案 0。

参考代码

练习 6:子数组的按位与之和

在线评测练习:P1519 子数组的按位与之和

题目描述

给定 n 个非负整数,求它所有连续子数组的按位与之和。

输入格式

第一行一个整数 n。

第二行 n 个非负整数,相邻两个整数之间用一个空格隔开。

输出格式

输出一个整数,表示所有连续子数组按位与的总和。

数据范围

  • 1 \le n \le 10^5。
  • 0 \le a_i < 2^{20}。

输入输出样例

输入

3
1 2 3

输出

8

子数组共 6 个:[1]=1、[2]=2、[3]=3、[1,2]=0、[2,3]=2、[1,2,3]=0,加起来是 8。

输入

3
5 5 5

输出

30

每个子数组的按位与都是 5,共 6 个,总和 30。

题目分析

这道题和练习 4 的区别是本章最关键的易错点:统计对象从「数对」变成了「连续子数组」。

  • 练习 4 数的是数对:正好两个数,方案数是 \binom{c_1}{2};
  • 这道题数的是子数组:长度可以是 1 到 n,方案数是把连续段累加。

两者都是「按位拆」,但方案数公式完全不同,绝不能互相套用——这正是易错点清单里「混用数对与子数组的公式」那一条。

按位看第 b 位:一个子数组的与在这一位为 1,当且仅当这个子数组里每个数在这一位都是 1。也就是说,这个子数组必须整段落在「这一位全为 1 的连续段」里。

于是做法很自然:扫一遍数组,把这一位为 1 的位置连成一段段。一段长度 len 里有 \frac{len(len+1)}{2} 个连续子数组,全部累加就是这一位为 1 的子数组个数,再乘 2^b。

这是本章例五的实现,和下一题(按位或)构成镜像:

  • 与:数为 1 的段,直接累加(条件苛刻,正好是连续 1);
  • 或:数为 0 的段,用「总数 −」(条件宽松,反着数更方便)。

最容易漏的一行是「最后一段的结算」。 循环结束时 len 里可能还存着一段的长度,如果只在遇到 0 时才结算,数组末尾那段就永远丢了。第二个样例 5 5 5 正是这种情况:所有位全是 1,len 从头累积到 3,一个 0 都没遇到,如果漏掉循环后的那一行,答案直接是 0。这也是本章易错点「分段统计漏掉最后一段」的典型翻车现场。

参考代码

练习 7(挑战):子数组的按位或之和

在线评测练习:P1515 子数组的按位或之和

题目描述

给定 n 个非负整数,求它所有连续子数组的按位或之和。

输入格式

第一行一个整数 n。

第二行 n 个非负整数,相邻两个整数之间用一个空格隔开。

输出格式

输出一个整数,表示所有连续子数组按位或的总和。

数据范围

  • 1 \le n \le 10^5。
  • 0 \le a_i < 2^{20}。

输入输出样例

输入

3
1 2 3

输出

15

子数组 6 个,或值分别为 1、2、3、3、3、3,加起来是 15。

输入

3
0 0 0

输出

0

题目分析

这是本章例二的完整实现,放在最后是为了和练习 5 形成完整对照。

按位看第 b 位:一个子数组的或在这一位为 1,当且仅当这个子数组里至少有一个数在这一位是 1。

「至少一个」不好直接数(要数「有 1 个 1 的、2 个 1 的、……」),于是用本章那条思维定式:反着数。

\text{这一位为 1 的子数组数} = \text{子数组总数} - \text{这一位全为 0 的子数组数}

子数组总数是 \frac{n(n+1)}{2};全为 0 的子数组数,就是把这一位为 0 的位置切成连续段,每段长度 len 贡献 \frac{len(len+1)}{2},累加起来。两者相减再乘 2^b。

和练习 5 对照着读,能看出本章那句「或统计 1 的补集、与统计 1 本身」的由来:

统计对象 运算 为 1 的条件 做法
数对 异或 两数不同 c_1 \times c_0
数对 与 两数都是 1 \dbinom{c_1}{2}
子数组 与 全是 1 数全 1 段,\sum \frac{len(len+1)}{2}
子数组 或 至少一个 1 总数 − 数全 0 段

同样别忘了最后一段。 第二个样例全是 0,如果漏掉循环后的结算,全零段数会被算成 0,「总数 − 0」就等于总数,答案会错得很大——反而比练习 5 的漏算更隐蔽。

另外注意 total 要用 1LL * n * (n + 1) / 2 算:n = 10^5 时约 5 \times 10^9,int 装不下。

参考代码

小结

贡献法的核心是换一个统计单位:不去枚举每个区间,而是统计每个元素参与了哪些区间。

它适用的信号很明确:题目要求「所有子区间的某个量之和」,而逐个区间算又是 O(n^2) 以上。

  • 元素 a_i(1-based)出现在 i \times (n - i + 1) 个连续子数组里。
  • 涉及位运算时,把每一位拆开,各自独立统计再合并。
  • 要求「每个元素作为最大值(或最小值)的区间数」,用单调栈求左右边界。
  • 数对型问题(异或和、差的绝对值和)也可以用贡献法,常常先排序或按位拆。
  • 乘积累加一律用 long long。

学完这一章,下面这些事应该能独立完成:

  • 说出贡献法与「枚举左右端点」的区别,并写出子数组和之和的 O(n) 解法。
  • 把异或和、或和、与和这类问题按位拆开,推导出每一位的贡献公式。
  • 写出单调栈求「左边第一个严格大于、右边第一个大于等于」的代码,并说清为什么要一边严格。
  • 对排序后的数组,说出 a_i 在「差的绝对值之和」里被算了多少次。
  • 分清「数对」与「连续子数组」两类统计对象:前者按 \binom{c}{2} 或 c_1 c_0 算方案,后者要对连续段累加 \frac{len(len+1)}{2}。
  • 记住四种按位组合的公式(数对异或/与、子数组与/或),并能说出「与数全 1 段、或数全 0 段」的原因。
  • 写出分段统计时不忘「最后一段要单独结算」。
Navigation

Type to search…

↑↓ navigate↵ selectEsc close