刷题刷到这个标题的时候我第一反应是又是 dp、又是线性筛、还要上数据结构题单是不是给错难度了等真正坐下来把题面读完才发现这题的核心其实非常朴素核心就是一道“等价变形 计数”的问题。这篇文章就把我当时完整的思考过程、代码实现和踩过的坑都写出来顺便聊清楚标题里那三个看似吓人的关键词到底哪些是本题真正需要的哪些又是同类问题里才会用上的。1. 先做一步代数变形把“物理碰撞”翻译成“差值相等”1.1 题面到底在问什么题目给了一个长度为 n 的排列也就是 1 到 n 每个数恰好出现一次。现在要统计满足下面条件的数对 (i, j) 的数量i j同时满足 i - j a[i] - a[j]我最初看到这个条件的时候脑子里全是“碰撞”“flag”这种具象画面觉得像是某种物理过程模拟。实际上它就是一个非常纯粹的代数条件两个位置的编号差恰好等于这两个位置上数值的差。举个例子n 4排列是 a [2, 3, 1, 4]。手动枚举所有 i j 的组合(1, 2)1 - 2 -1a[1] - a[2] 2 - 3 -1满足(1, 3)1 - 3 -2a[1] - a[3] 2 - 1 1不满足(1, 4)1 - 4 -3a[1] - a[4] 2 - 4 -2不满足(2, 3)2 - 3 -1a[2] - a[3] 3 - 1 2不满足(2, 4)2 - 4 -2a[2] - a[4] 3 - 4 -1不满足(3, 4)3 - 4 -1a[3] - a[4] 1 - 4 -3不满足所以这个排列的答案是 1。这个枚举过程能让我们非常直观地感受到每一对都要做一次减法和一次比较如果直接两层循环复杂度是 O(n²)。题目的 n 如果到十万、上百万这个复杂度肯定完蛋。必须想办法把“两两比较”变成“一次归类”。1.2 移项之后的世界把条件 i - j a[i] - a[j] 挪一下得到i - a[i] j - a[j]这个移项是整道题最关键的一步。等号两边稍微一变整个问题的形态就完全不同了。原来我们需要两两比较两个位置的信息现在只需要给每个位置算一个独立的数d[i] i - a[i]然后问题就变成了统计有多少对位置 i j使得 d[i] d[j]。“两两比较”变成了“看哪些位置的 d 值相等”这是一个从 O(n²) 到 O(n) 的关键转折。我每次给初学者讲这题都说遇到等式先把下标和值分别往两边放凡是形如 f(i) f(j) 的计数题十有八九是用桶或者哈希把相同键值归类。回到刚才那个例子d[1] 1 - 2 -1d[2] 2 - 3 -1d[3] 3 - 1 2d[4] 4 - 4 0差值 -1 出现在位置 1 和 2正好对应那个满足条件的数对。其余差值都只出现一次没有配对。1.3 从“数对”到“桶”答案等于组合数现在问题的规模清晰了n 个位置每个位置算出一个 d[i]数值可能重复。如果某个差值 x 一共出现了 cnt 次那么这 cnt 个位置里任意选两个都能组成合法数对所以贡献是C(cnt, 2) cnt * (cnt - 1) / 2最终答案就是所有差值出现次数的组合数之和。为什么是组合数而不是排列数因为题目要求 i j也就是说两个位置是有顺序约定的但一对位置只有一种合法的先后排列。从 cnt 个位置里选出两个大的下标放到后面这就是唯一的一种配对所以用组合数。到这一步暴力枚举已经被彻底消掉了。剩下的任务只有一个数一数每种差值出现了多少次。所有解法都围绕这个“统计频次”展开差别只在于你用什么容器去存频次。2. O(n) 桶计数就是全部答案一份代码和三种写法2.1 差值值域分析与偏移既然要用桶统计频次第一个问题就是差值 d[i] 的范围到底有多大题目保证 a[i] 是 1 到 n 的排列所以每个 a[i] 都在 [1, n] 里。那么d[i] 的最小值i 取 1a[i] 取 n得到 1 - nd[i] 的最大值i 取 na[i] 取 1得到 n - 1也就是说所有差值都落在 [1 - n, n - 1] 这个区间里总共有 2n - 1 种可能。这是一个非常窄的值域直接开一个长度为 2n 左右的数组就能装下。但数组下标不能是负数所以需要一个偏移量。我用 off n把差值 d 映射到下标 d nd 1 - n 时d n 1d n - 1 时d n 2n - 1这样下标就落在 [1, 2n - 1]数组开 2n 5 完全够用。这个偏移操作看着不起眼但实际写代码时特别容易漏漏了之后要么越界要么结果全错后面我会专门再讲。2.2 完整实现下面这份代码是核心解法复杂度 O(n)空间 O(n)。我保留了注释方便对照着看。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint a(n 1); for (int i 1; i n; i) { cin a[i]; } // 差值范围 [1-n, n-1]偏移 n 之后映射到 [1, 2n-1] vectorint cnt(2 * n 5, 0); int off n; long long ans 0; for (int i 1; i n; i) { int d i - a[i]; // 当前差值之前已经出现多少次就新增多少对 ans cnt[d off]; // 当前这个位置加入桶 cnt[d off]; } cout ans \n; return 0; }这段代码里最关键的地方不是累计组合数公式而是那个ans cnt[...]加在更新之前的顺序。第一次遇到某个差值 x 时cnt[x] 是 0ans 加 0第二次遇到同一个差值时cnt[x] 已经变成 1ans 加 1表示新增了和之前那个位置的一对第三次遇到时 cnt[x] 是 2ans 加 2新增两对。整个过程等价于对 cnt 做组合数累加但省掉了最后再遍历桶的循环。这种“先查再增”的顺序是这类计数题里特别惯用的手法等于把每个元素对答案的贡献分散到插入时计算整个流程一遍扫下来答案就齐了。2.3 三种写法的对比数组桶并不是唯一的写法。根据场景不同还有另外两种常见实现我把它们列在一起对比。写法思路时间复杂度空间复杂度适用场景数组桶值域小直接用下标当差值O(n)O(n)排列类题目值域连续且窄排序分组把所有差值排个序相同值聚在一起O(n log n)O(n)值域稀疏但可以离线哈希表用 unordered_map 存差值到频次期望 O(n)O(n)差值可能非常大且不连续数组桶优势明显访问是严格 O(1)内存连续Cache 友好常数极小。排序分组适合值域无法预测的情况但会引入 log 复杂度在 n 很大的时候效率一下子就被数组桶拉开。哈希表在工程里最灵活可它的随机访问模式对 Cache 不友好常数偏大竞赛场景下能开数组就优先数组。2.4 为什么排序不是必要步骤有人可能会问既然最后要统计重复差值那先把差值数组排序再扫一遍相同段不也能算出来吗当然可以这个思路没错但它不是最优解。排序能做是因为“重复值会聚在一起”这个性质但排序本身需要 O(n log n)。而我们明明已经知道差值被限制在一个极窄的整数区间里数组下标天然就把这个“聚集”完成了。值域窄到可以直接映射就没必要让所有数据先经过比较排序再聚堆。这是典型的“用空间换时间”用一个 O(n) 的数组换来比排序低一个数量级的时间开销。3. 标题里的“数据结构”其实从桶就开始了3.1 桶在数据结构体系里的位置很多人一看到“数据结构”四个字就自动联想到线段树、平衡树、树状数组这些高级货反而把最基础的桶忘在一边。其实桶就是一种数据结构它解决的核心问题是“按键值快速存取频次”。数组桶、哈希表、字典本质上都是同一类东西给你一个键你告诉我有多少。P4889 这道题用到的数据结构就是最简单的数组桶。它的操作只有两个按下标加一、按下标取值。这两个操作被压缩在“先查再增”的两行代码里数据结构没有消失只是由于值域小实现被简化成了数组。这样说可能会让一些读者失望怎么“数据结构”题就一个数组但我觉得恰恰相反能把数据结构简化成数组说明题目把最核心的算法思想留给了你而不是让你花大把时间在维护复杂的树上。数据结构是手段不是目的。3.2 树状数组视角把桶打个升级补丁如果硬要从树状数组的角度去看也不是不行。假设我们不使用数组桶而是用树状数组维护每个差值出现的频次那逻辑会变成这样每来一个位置 i先查询当前差值 d 已经累计了多少次加到答案里然后给这个差值做一次单点加一update(d, 1)树状数组支持单点更新和前缀和查询单次操作 O(log n)整体复杂度 O(n log n)。相比数组桶的 O(n)反而变慢了。为什么变慢因为这里每次查询都只关心单个差值的精确频次不涉及区间求和树状数组的前缀和优势完全发挥不出来。桶能 O(1) 完成的事非要套个 log 的数据结构属于杀鸡用牛刀。但树状数组视角有一个好处它把“数据结构通用接口”抽象出来了。假设将来问题不是“全局统计”而是“区间内统计”数组桶无法直接处理更新和查询的时序关系那时候树状数组的 log 就变成必须付出的代价而不是额外的开销。3.3 变式区间查询才是数据结构真正登场的地方把原题改一下问题立刻变难给定若干个查询 [L, R]要求统计满足 L i j R 且 d[i] d[j] 的数对数量。这时候如果你还只开一个全局桶扫描到 R 时桶里混着所有小于 R 的信息你没法把 L 左边的部分剔除掉。全局数组桶已经不够用了因为它的信息没有“位置标记”无法按区间切割。这种问题需要更精细的手段常见思路是离线处理配合树状数组或者莫队把所有查询按右端点 R 排序从左到右扫描原数组每扫描到一个位置 i就把它的差值 d[i] 的频次信息挂到树状数组/桶上回答某个查询 [L, R] 时只使用位置 L 的信息这已经是比较典型的二维偏序模型了代码量会比原题大不少。标题里那个“数据结构”在这类变式里才是真正的必需品。原题没有走到这一步只是因为它不需要区分位置区间全局一桶到底就行。4. 标题里的“dp”和“线性筛”它们不是本题必需品却是同类题通用武器4.1 dp 思想藏在“边扫描边累加”里严格来说P4889 并不需要动态规划。但如果我们较真去看那份“边扫描边累加”的代码它其实带着很浓的 dp 味道。设想一个更朴素的状态定义dp[i][x] 表示扫描完前 i 个位置后差值 x 已经出现的次数。转移方程是如果 d[i] x则 dp[i][x] dp[i-1][x] 1如果 d[i] ! x则 dp[i][x] dp[i-1][x]所有位置都只关心当前差值和其他差值无关所以这个二维状态根本不需要完整保存滚动数组一压就剩下一个一维数组 cnt。再往后想连枚举 x 的循环都不需要因为每步只更新一个固定的 d[i]最终的答案就是每个 x 的 C(dp[n][x], 2) 求和。你看一个看起来不像 dp 的解法底层逻辑和动态规划是完全同构的。理解这一点之后遇到真正需要 dp 的变式就不会慌比如如果差值不再是一个定值而要根据前面若干位置的状态共同决定那时 dp 就会从“隐形”变成“显性”。4.2 线性筛什么时候会跑出来线性筛在本题里也没有出现。它的典型用途是预处理质数、欧拉函数、莫比乌斯函数这些数论函数复杂度 O(n)并且能保证每个合数只被筛一次。为什么要提它因为很多和差值、计数相关的题目最后会叠加一个数论条件。举个例子。假设题目改成统计满足 d[i] d[j] 且 |i - j| 是质数的数对。你仍然可以用桶把同差值的下标收集起来但每一组同差值的下标里不再是随便两两都能配对必须额外检查下标距离是否为质数。为了快速判断你需要一张一直到 n 的质数表而生成这张表最高效的方式就是线性筛。再比如变式里需要预处理阶乘和逆元来算组合数那也是线性筛的亲戚线性递推求逆元本身和筛法有相似的内存访问模式。很多“计数 数论限制”的题线性筛就藏在预处理阶段它不直接参与核心的计数逻辑却是整个解法能跑起来的地基。4.3 当三个词同时出现时题目长什么样结合上面几点标题里三件套真正同时登场的题目通常是这种骨架定义了一个由位置和值共同决定的特征量 d[i]要求统计 d[i] d[j] 且满足额外条件比如某个函数值是素数、某个前缀和限制的对数额外条件依赖的数论函数要用线性筛预处理计数过程需要按某种顺序递推避免重复这就是 dpP4889 恰好把这个骨架里的所有附加条件都删掉了只剩下最核心的第 1 条和第 2 条的简单形式。所以它不需要 dp 也不需要线性筛一个桶就结束。但这并不意味着标题写错了它更像是在暗示这道题是那个更复杂模型的一个“最小可运行版本”。我个人的习惯是拿到这种挂着多个算法标签的题先做减法找出哪些标签是吓唬人的哪些是真正的考察点。P4889 的考察点就是代数变形和值域分析把这两步想清楚代码只是顺手的事。5. 实测中容易踩的坑和两个扩展方向5.1 负下标、精度、读入三个小坑第一个坑是负下标。差值 d[i] i - a[i] 在排列中经常是负数如果你直接用 cnt[d[i]]下标瞬间越界。我见过太多第一次写这题的同学挂在这一点上。解决办法就是给下标加一个偏移但要记得偏移量必须覆盖整个负值区间不能只加一点点。第二个坑是精度。答案最大能到多少n 个位置最多产生 C(n, 2) 对数当 n 10^6 时这个值大约 5 x 10^11远超 32 位整数范围。所以答案变量必须用 long long而频次桶因为每个位置最多贡献一次int 就够用。这个细节在本地小数据测试时根本暴露不出来一旦加大数据立刻爆掉。第三个坑是读入。n 到百万级别时cin 不关同步是有点慢的建议加上ios::sync_with_stdio(false)和cin.tie(nullptr)或者直接写快读。虽然现在很多评测环境对 cin 的优化很好了但这种 O(n) 扫一遍的题输入开销占比很大一点常数优化都可能是 TLE 和 AC 的差距。5.2 模数与取模姿势有些版本会把答案要求对某个模数取模。这时候要注意累加过程中每步都可能溢出不能等最后再取模MOD 1000000007 每轮ans (ans cnt[d off]) % MOD取模之后 cnt 本身不需要取模它只是一个频次计数最大不会超过 n。但如果题目给的 n 特别大cnt 也可能到 int 上限边缘稳妥起见可以直接把 cnt 定义成 int因为 10^7 以内都没问题更大的数据再用 long long。还有一个容易忽略的细节如果你把ans cnt[...]改成先累加再取模要保证中间的加法和乘法不会溢出 long long。对于 n 在 10^6 这个量级单次累加不会超范围但如果你改成计算 C(cnt, 2) 后求和cnt * (cnt - 1)本身要先取模再做除法不然可能爆。5.3 扩展一序列不是排列时原题条件里“排列”这个信息非常重要它保证了值域连续且有限。如果把排列改成普通数组a[i] 可以是任意整数差值范围就不可控了如果 a[i] 在 [1, 10^9]差值可能覆盖几十亿的范围数组开不下这时候必须换成哈希表或者先排序再归组哈希表的做法很简单unordered_mapint, int cnt遇到 d 就cnt[d]同时累加答案。代码逻辑几乎一样只是底层容器变了。复杂度期望 O(n)但常数比数组桶大数据量大时要注意。如果不用哈希表也可以用排序把 n 个差值放进一个数组排序后相同的值会聚成连续段对每一段长度 len 累加 C(len, 2)。这个做法空间占用低时间 O(n log n)在内存受限的评测环境下经常是更好的选择。5.4 扩展二从统计对数到支援其他计数这个“差值相等”模型还能演进成不少变体。比如统计 d[i] d[j] 且 i j 满足某种条件统计 d[i] d[j] 的最远距离每个 i 只能参与一次配对问最多能配成多少对拿“最远距离”来说只需要维护每个差值第一次出现的位置 first[x] 和最后一次出现的位置 last[x]答案取 max(last[x] - first[x])复杂度 O(n)。拿“最多配对”来说每个差值出现次数除以 2 向下取整后累加即可。这些变体的共同点都是先按 d 值归类然后再对组内做各种统计。只要把“差值相等”这个核心模型吃透了遇到类似的题就是换汤不换药。我自己刷这道题最大的收获其实是养成了一种思维习惯看到计数条件里有 i 和 a[i] 纠缠在一起的等式第一反应永远是尝试把下标和值分离到等号两边变成 f(i) g(a[i]) 再继续想。这个习惯在这次是用桶换一道题可能就是用哈希、用排序、用树状数组。数据结构永远只是工具决定解题方向的永远是那一步代数化简。