
有一类题目的字面要求是「所有子区间的某种量加起来是多少」。按字面去做,枚举所有区间是 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输出
30n=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输出
31 \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 段」的原因。
- 写出分段统计时不忘「最后一段要单独结算」。