P3396 哈希冲突题目名字自带迷惑性——乍一看像是在考哈希表的开放寻址、拉链法那些东西实际上洛谷这道“普及/提高−”难度的题根本不让你写哈希表而是考察根号分治sqrt decomposition这个看似简单、实则极其经典的优化套路。题面一句话就能说清维护一个数组每次操作要么把某个位置的值改掉要么询问“所有下标对 x 取模等于 y 的元素之和”。我第一次做的时候也以为暴力就能过结果一提交直接被 TLE 教做人才意识到小范围暴力、大范围预处理的分治思想才是正解。如果你是正在刷普及组往提高组过渡的 OIer或者对“分块暴力美学”感兴趣的选手这题很适合拿来入门根号分治。它不需要任何高级数据结构的铺垫只要你会 C 的数组、循环和一点复杂度分析就能把思路完全打通。下面我直接把题目拆开从为什么暴力会超时到根号分治的原理再到完整 C 实现最后把我踩过的坑和调试经验一并分享出来。1. 题目背景与核心思路1.1 题意复盘顺便聊聊这个奇葩名字先简单交代一下题目说了什么。给定一个长度为 n 的数组 a下标从 1 开始有 m 次操作每次操作有两种查询操作A x y求所有满足i % x y的下标 i 对应的 a[i] 之和即求出所有权模 x 余 y 的元素的总和。修改操作C x y把 a[x] 的值改为 y。我手写一个小的例子来演示。假设初始数组是1 2 3 4 5查询A 2 1就要把下标 1、3、5 的值加起来得到1 3 5 9。如果这时候修改C 3 10数组变成1 2 10 4 5再次查询A 2 1答案就变成1 10 5 16。题目本身没有任何弯弯绕绕。那为什么叫“哈希冲突”呢在哈希表里哈希函数经常就是取模运算比如h(key) key % p多个 key 映射到同一个桶时就会发生冲突。这道题里的i % x本质上就是一个取模哈希函数把下标 i 分到了“余数为 y”的桶里询问就是问某个桶里所有元素的和。所以这个题名不是让你解决哈希冲突而是反过来——利用“冲突”之后形成的分组去快速回答区间统计问题。搞懂这层对应关系再看题目就亲切很多。1.2 为什么朴素暴力一定会超时先聊聊最直觉的暴力做法。对于查询操作直接在y开始每次步长加x从头扫到尾累加int ans 0; for (int i y; i n; i x) { ans a[i]; }修改操作就更简单了a[x] y一下就完事。这个写法的代码量大概是全场最短路程但复杂度极其感人一次查询在最坏情况下要遍历所有 n 个元素也就是 O(n)。如果来了 m 次查询总复杂度就是 O(n·m)。洛谷这题的 n 和 m 上限都在 150000 左右乘起来是 2.25×10^10这个量级哪怕 C 跑一两秒也完全顶不住更别说题目经常有专门卡暴力的数据。所以必须另想办法。1.3 根号分治的直觉两边下注谁都不亏根号分治的核心直觉其实特别朴素把操作对象按照某个阈值分成“大”和“小”两类小的一类用预处理换时间大的一类干脆直接暴力最后两边的单次复杂度都被压在根号级别。放在这道题里查询的模数 x 就是分类依据。当 x 很小的时候余数种类少我们就提前把所有“模 x 等于 y 的元素和”全部算好存起来查询时直接查表O(1) 搞定当 x 很大的时候满足条件的下标其实没几个因为每隔 x 个位置才有一个直接暴力枚举也花不了多少时间。两边的复杂度都能控制在 O(√n) 左右整体自然就快起来了。这个思想很像生活中“小问题走流程大问题走特殊通道”的处理方式。小模数查询频率高、数据量集中值得花空间存结果大模数查询涉及的元素稀疏存表反而浪费直接现场算更划算。下面我把这个思路拆成两个部分讲清楚预处理和暴力分别在干什么。2. 根号分治原理拆解2.1 小模数预处理把答案提前算好选一个阈值 S一般取sqrt(n)附近。对于所有x S的查询我们需要一个能 O(1) 回答的数据结构。定义二维数组f[i][j]表示“所有下标对 i 取模等于 j 的元素之和”其中i从 1 到 Sj从 0 到 i-1。初始化的方法很直接遍历数组中的每个元素 a[pos]把它加到所有f[i][pos % i]里面去。举个例子n5S2初始数组1 2 3 4 5。初始化时对 i1所有元素模 1 都等于 0所以f[1][0] 12345 15对 i2下标 1、3、5 模 2 等于 1f[2][1] 135 9下标 2、4 模 2 等于 0f[2][0] 24 6初始化之后查询A 2 1直接输出f[2][1]即可。修改操作同样好办把 a[pos] 从旧值改成新值只需要算出差值 delta然后把所有f[i][pos % i]都加上 delta。因为模数 i 最多只有 S 个所以修改操作是 O(S) 的也就是 O(√n)。2.2 大模数暴力稀疏到直接扫也不慢对于x S的查询我们放弃查表直接在原数组上跳着累加for (int i y; i n; i x) { ans a[i]; }可能有朋友会担心这不是又回到暴力了吗其实不会。因为每次下标至少增加 x而 x 大于 S所以整个循环最多执行n / x次由于 x S ≈ √n这个次数小于n / √n √n。换句话说一次大模数查询最多也就扫 √n 个元素和预处理的代价是同一个量级完全在接受范围内。这个思路非常符合根号分治的“对称美”小模数查询靠预处理做到 O(1)代价是修改 O(√n)大模数查询靠暴力做到 O(√n)修改则只需要直接改原数组 O(1)。两边互相补充整体复杂度被牢牢按在 O(√n) 级别。2.3 阈值为什么取根号 n数学账一算就明白总有人会问为什么阈值不取 100 也不取 1000偏偏是 √n这里可以做一个小推导。假设阈值为 S那么预处理数组的大小是 O(S²)修改复杂度 O(S)小模数查询 O(1)。大模数查询时最坏情况要枚举n / x次而 x S所以最多是 O(n/S)。一次操作的最坏复杂度就是max(S, n/S)这个量级。初中不等式告诉我们当 S n/S 时也就是 S √n这个最大值最小等于 √n。阈值取得太大预处理数组和修改开销会膨胀取得太小大模数暴力又拉了胯。所以理论最优解就是取sqrt(n)附近。实际写代码时为了避免浮点误差我一般取sqrt(n) 1后面会说为什么这样更稳。3. C 代码实现与关键细节3.1 数据结构定义与空间估算先看核心的数据结构定义#include bits/stdc.h using namespace std; const int MAXN 150005; const int MAXS 400; // 阈值大致取 sqrt(150000)1 ≈ 388开 400 稳妥 int n, m, S; int a[MAXN]; int f[MAXS][MAXS]; // f[i][j] 表示下标模 i 余 j 的元素和f数组我直接用静态二维数组第一维是模数第二维是余数。这里有个细节f到底要开多大如果 S 取 388那么最大模数是 388余数 j 的范围是 0 到 387所以开MAXS × MAXS完全够用f[388][387]不会越界。整个数组大小是 400×400160000 个 int大概 640KB内存开销可以忽略不计。至于为什么用 int 不用 long long是因为这题的数据范围求和不会超过 int 上限。如果你不放心或者题目数据更强可以直接全部换成 long long代价只是内存翻倍逻辑完全不变。3.2 读入与预处理预处理是整个算法正确性的基石。代码写在读入数组之后int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; for (int i 1; i n; i) { cin a[i]; } // 确定阈值加 1 是为了防止边界误差 S sqrt(n) 1; // 预处理所有小模数的分组和 for (int i 1; i n; i) { for (int p 1; p S; p) { f[p][i % p] a[i]; } } // 之后处理 m 次操作 }预处理的双层循环里外层枚举每个元素内层枚举所有模数 p。对于固定的 a[i]它对所有 p 的贡献都是加到f[p][i % p]这一个格子里所以内层循环天然就是 O(n·S) 的。当 n150000、S388 时循环次数约 5800 万次C 在 1 秒左右能跑完这个代价是值得的因为它换来了后面海量查询的 O(1) 回答。3.3 修改操作的 delta 增量法修改操作是这题最容易写崩的地方。很多人会直接重新初始化整个 f 数组那复杂度直接拉满。正确做法是只更新受影响的格子while (m--) { char op; int x, y; cin op x y; if (op A) { // 查询操作 if (x S) { cout f[x][y] \n; } else { int ans 0; for (int i y; i n; i x) { ans a[i]; } cout ans \n; } } else { // 修改操作 int delta y - a[x]; if (delta 0) continue; for (int p 1; p S; p) { f[p][x % p] delta; } a[x] y; } }修改操作利用的是“整体增量”的思路。a[x] 从旧值变成新值差值 delta 对每个模数 p 来说只需要加到f[p][x % p]上因为只有这个格子包含了旧 a[x] 的贡献。这个技巧避免了重新扫描整个数组也是根号分治里“修改 O(√n)”的来源。有一个小细节特别容易被忽略if (delta 0) continue;。虽然这个判断不影响正确性但能减少无意义的循环尤其当修改的数据恰好和原值相同时省掉一整轮 O(S) 的更新。竞赛里数据一大这种不起眼的常数优化往往就是 AC 和 TLE 的分水岭。3.4 查询操作的边界与越界思考查询时模数 x 分成两种情况x S直接输出f[x][y]x S则暴力枚举。这里要注意输入保证0 y x所以查表时下标 y 一定合法。暴力分支的循环从i y开始每次加 x。细心的读者可能会发现如果 y 0循环第一次会访问a[0]。因为我们把a定义成全局变量a[0]自动初始化为 0不会影响累加结果所以代码是安全的。但如果你把a定义在main函数内部一定要记得手动把a[0]赋值为 0否则未初始化的局部数组会给你一个随机垃圾值答案直接错得离谱。i x的循环终止条件是i n这个写法比i n的 while 循环更简洁也更能体现“步长为 x 跳着访问”的意图。而且当 x 大于 n 的时候这个循环最多执行 1 次恰好符合“大模数查询元素极少”的直觉。3.5 完整代码与复杂度一览把上面的片段拼起来就是完整可提交的代码。我再补一个可读性更好的版本#include bits/stdc.h using namespace std; const int MAXN 150005; const int MAXS 400; int n, m, S; int a[MAXN]; int f[MAXS][MAXS]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; for (int i 1; i n; i) { cin a[i]; } S sqrt(n) 1; for (int i 1; i n; i) { for (int p 1; p S; p) { f[p][i % p] a[i]; } } while (m--) { char op; int x, y; cin op x y; if (op A) { if (x S) { cout f[x][y] \n; } else { int ans 0; for (int i y; i n; i x) { ans a[i]; } cout ans \n; } } else { int delta y - a[x]; if (delta 0) continue; for (int p 1; p S; p) { f[p][x % p] delta; } a[x] y; } } return 0; }复杂度总结如下预处理O(n·S) O(n√n)修改操作O(S) O(√n)小模数查询O(1)大模数查询O(n/S) O(√n)总空间O(n S²)当 n 和 m 都是 150000 时整体运算量远小于暴力解法的 2.25×10^10洛谷实测能稳定过掉。4. 常见问题与调试经验4.1 数组越界以及 f 的两种经典翻车写法很多新手在初始化 f 的时候会把两个循环的顺序写反。写成下面这样for (int p 1; p S; p) { for (int i 1; i n; i) { f[p][i % p] a[i]; } }这个顺序其实没问题效果和先遍历 i 再遍历 p 完全一样。真正容易越界的是 f 数组的第二维。假如你开了f[MAXS][MAXS]但模数 p 取到了 MAXS-1那么i % p的最大值是 p-1也就是 MAXS-2不会越界。可如果你手滑把f[p][i % p]写成了f[p][i % MAXS]那当 i % MAXS 超过 p 的取值范围时就会访问到“当前模数理论不存在的余数位置”虽然不一定会 RE但答案会错得莫名其妙。所以第二维下标一定要用i % p不能偷懒用固定模数。另外S 取sqrt(n)不加 1 也是隐患。假如 n 是 150000sqrt(150000)约等于 387.3取整是 387。此时预处理只覆盖到模数 387但查询如果出现 x388 而 S387程序会走暴力分支所以不会错。真正危险的是你初始化循环里写了p S而查询分支判断用x S这样 xS 时走了暴力分支但在预处理时 pS 又确实算过两边不一致就会产生逻辑混乱。统一用x S和p S然后 S 取sqrt(n) 1是最省心的做法。4.2 输入输出与卡常的实战经验洛谷这类题的数据量不算小m 可能有 15 万次操作每次查询都要输出一行如果还用默认的cin/cout不关同步很容易超时。我习惯在代码开头写ios::sync_with_stdio(false); cin.tie(nullptr);这两行几乎是所有 C OI 题的保命符。第一个关闭了 C 标准流和 C 标准流的同步第二个取消了 cin 和 cout 的绑定让输出不用每次强制刷新缓冲区。如果这样还怕卡常可以直接换scanf/printf配合char op; int x, y;也完全没问题。4.3 修改操作遗漏更新原数组调了一晚上才发现的坑这个坑是我自己踩过的。写修改操作时我先更新了所有f[p][x % p]然后直接进入下一轮循环忘了写a[x] y。结果下一次修改同一个位置时delta 是用旧值算出来的导致所有 f 叠加了两次增量数据全乱。这个问题非常隐蔽因为前几次查询可能碰巧是对的等修改次数一多答案就完全对不上了。所以修改操作的正确顺序是先计算 delta 并更新所有 f最后再更新 a[x] 本身。更保险的做法是一开始就记录旧值哪怕写完忘了一步也能通过旧值和新值的对比快速发现问题。调试的时候我建议自己手写一个小的随机数据生成器用暴力算法跑一遍标准答案再和根号分治版对拍几秒钟就能定位问题所在。5. 聊聊这类思想还能用在哪根号分治其实不只是一个解题套路它还是一种非常通用的工程优化思维。凡是遇到“查询和修改相互矛盾”的问题——查询想快就得预存信息预存信息后修改就变慢反之亦然——都可以考虑用阈值把操作分成两类。比如统计区间众数、动态维护某个偏序关系、甚至一些数据库索引设计里都有类似的“空间换时间”权衡。刷完 P3396 之后我个人认为最大的收获不是背会了模板代码而是建立了“看到取模就想到分治”的条件反射。以后再遇到和模数、余数、分组统计相关的问题时第一反应不再是傻傻暴力而是先想“模数小的时候能存什么模数大的时候暴力枚举多少次”。这套思维模型在各种 OI 题里会反复出现值得多花时间吃透。最后分享一个小技巧如果你刷完模板题的代码想检验自己到底理解了多少可以试着把阈值从sqrt(n)1改成n/2或10通过这题的大数据测试你会直观地感受到不同阈值带来的性能差异。我自己试过把 S 调到 1000结果预处理慢到肉眼可见调到 10又会被大模数查询的暴力循环拖垮。亲手对比一次比看一百行推导都印象深刻。
