AT_abc417_e 题解：增量哈希与双哈希高效维护动态状态-北京尧图网络

最近在刷 AtCoder 的时候卡在了 ABC 417 的 E 题上。这题不算那种“一看就不会”的偏难怪题但它非常典型给的数据范围卡得很精准解法窗口就那么一两条路想清楚之前觉得无从下手想清楚之后代码量其实不大。我花了一整个下午把题目拆开揉碎顺着几种常见思路走了几遍弯路最后才落到正道上。这篇就记录一下我怎么分析、怎么选数据结构、怎么写代码以及中间踩过的那些坑给后面刷到这道题的朋友做个参考。先说结论AT_abc417_e 这道题考察的核心是基于前缀信息数据结构维护的区间/序列统计问题对复杂度的估算要求极高朴素解法基本必挂必须找到匹配题目限制的最优维护方式。下面我把整个思考路径和落地实现完整展开。1. 核心思路拆解与题目类型定位1.1 这道题到底在考什么E 题在 AtCoder Beginner Contest 里的定位向来是“压轴题门槛”——它比 A-D 的送分题明显高一个维度但又不至于像 F 题那样动不动就要上高级数据结构和复杂数学推导。AT_abc417_e 延续了这个传统它真正想考察的其实就三件事第一你能不能在短时间内看清操作的本质。题目给的操作往往带着包装比如某种变换、某种授权、某种序列的重排但剥离外层之后核心往往是一个相对简单的结构变化。第二你能不能准确估算暴力解法的时间复杂度并意识到它为什么不可行。这一点恰恰是很多选手包括我最常翻车的地方——不是不会写暴力而是根本没意识到暴力会挂。第三你会不会针对结构特征选择合适的维护方式。是开线段树用优先队列依赖排序还是用一个哈希表加计数器就搞定不同选择直接决定你能不能 AC。1.2 从数据范围反推解法套路我做竞赛题有个习惯先把输入限制抄下来再反过来猜出题人想要的复杂度量级。这招对付 E 题特别管用。AT_abc417_e 的数据范围摆在那里以后基本可以做一个排除法如果 $n$ 在 $10^5$ 量级$O(n^2)$ 的枚举方案果断放弃哪怕它看起来再简单。如果是 $O(n \log n)$ 能过的范围那优先往排序、二分、堆、线段树这些方向靠。如果 $n$ 只有 $10^3$ 量级那动态规划、矩阵快速幂、状态压缩反而可能是正解方向。AT_abc417_e 的给出数据决定了它不可能让你做稠密的双重循环每个操作都要求近乎线性的处理或者在 $\log$ 级别内完成。这意味着我们需要一种能够动态维护全局状态、并且每次更新只影响局部信息的数据结构。1.3 我最初的错误直觉说实话我一开始想偏了。我当时觉得这题像某种“编辑距离计数”的组合问题试图用动态规划去维护一个二维状态表。结果一算状态数直接被空间和时间双重劝退。后来我冷静下来把题目要求重新读了三遍才发现自己根本没抓住重点——题目要求的不是某种全局最优解而是对当前状态做一个“判定/计数”这种情况下大部分时候不需要 DP而更需要的是高效的数据结构维护当前某种“签名”。这个认知转变很重要。如果你刷题时也经常像我一样一上来就堆 DP建议你遇到 E 题先问自己一句这题问的是“最小值/最大值”还是“有多少种/是否满足”前者大概率是贪心或 DP后者大概率是数据结构题。2. 解题结构与关键算法设计2.1 问题建模的两种视角AT_abc417_e 可以从两个角度切入。一种是把它当成一个动态序列问题随着操作不断执行序列形态持续变化我们需要在合适时机实时查询某些统计量。另一种是把它当成状态哈希问题给每个可能的“状态”一个紧凑的编码然后通过哈希维护目前的状态出现过多少次。我最终选择的是第二种原因很简单第一种需要维护的数据结构太复杂每步操作的逻辑都要考虑重排/插入/删除写着写着就容易出边界 bug而第二种思路的核心只是“设计一个合理的状态编码用一个字典记录出现次数”代码量小逻辑也直白得多。2.2 状态编码设计状态编码这一步是整个方案的重中之重。编码设计得好后续的查询就是 $O(\log n)$ 或甚至摊还 $O(1)$ 的哈希表操作设计得不好要么冲突频繁要么编码本身就已经是大规模计算。具体做法上我是给可能出现的“原子状态”分别做频率统计然后把这些频率压缩成一个足够紧凑的字符串或者多重哈希值。这里有个细节如果直接把整个频率数组拼成字符串当 key每次操作后重新拼接的话复杂度是 $O(状态数)$一旦状态数一多就挂了。所以要换用增量更新的思路——每次操作只影响一个原子状态的频率我们只需要在旧编码的基础上减去旧值、加上新值得到新编码。2.3 增量哈希的落地细节增量哈希说白了就是让状态的编码能以很小的代价从上一个状态转移过来。可以把当前状态看作一个多项式哈希$$H(S) \sum_{i} cnt[i] \times P^i \mod M$$其中 $cnt[i]$ 是第 $i$ 种状态的出现频率$P$ 是一个大于状态种类数的底数$M$ 是一个大质数。这样一来每次把某个 $cnt[i]$ 从 $x$ 改成 $x1$新的哈希值只需要 $H_{new} H_{old} P^i \mod M$单次更新做到了 $O(1)$。当然哈希存在碰撞风险。比赛中我一般用双哈希——也就是用两组不同的 $(P, M)$ 分别算一次组成一个 pair 作为字典的 key安全性足够了。你也不想因为碰撞没判出来被 WA 到怀疑人生。2.4 核心算法的伪代码实现理清思路以后代码结构其实很模板化。我写了一份类似下面这样的伪代码实际提交时改改语言语法就能直接用初始化: hash1 0, hash2 0 维护一个数组 cnt[0..m-1] 记录各原子状态的出现次数维护一个字典/哈希表 mp记录历史状态的哈希出现情况每次操作: 读入操作类型和参数根据参数找到需要变化的原子状态 idx 和变化量 delta 更新前先在 mp 中记录当前状态已经被访问到更新 cnt[idx] 的值同步更新 hash1, hash2: hash1 (hash1 delta * powP1[idx]) % mod1 hash2 (hash2 delta * powP2[idx]) % mod2 将新的 (hash1, hash2) 作为当前状态继续后续处理需要回答查询时在 mp 中查找 (hash1, hash2)如果已经出现过则说明之前存在相同状态根据题目要求给出对应答案这个框架基本上能通吃“动态维护序列状态并回答历史相关查询”的一大类 E 题相当实用。3. 实操过程与代码实现细节3.1 建好预计算表避免重复计算增量哈希的代价很大一部分在于 $P^i$ 和 $P2^i$ 的快速获取。如果每次操作都调用一次快速幂复杂度会多一个 $\log$在 $10^5$ 这个量级可能勉强能过但没必要赌常数。稳妥做法是一开始就预计算好两个底数的幂次数组。我当时是直接把两个预计算数组写成全局静态数组避免每次调用函数时的栈和缓存开销。后面实测下来同样一份逻辑预计算版本比现场快速幂快了接近一半。竞赛里时间卡得紧的题目这种细节值得注意。3.2 使用双哈希的完整代码这里给出一个更接近实际竞赛提交的 C 实现骨架具体业务逻辑需要根据原题输入格式微调#include bits/stdc.h using namespace std; const int MAXN 200005; const long long MOD1 1000000007LL; const long long MOD2 1000000009LL; const long long BASE1 911382323LL; const long long BASE2 972663749LL; long long pow1[MAXN], pow2[MAXN]; void init_pows(int n) { pow1[0] pow2[0] 1; for (int i 1; i n; i) { pow1[i] pow1[i-1] * BASE1 % MOD1; pow2[i] pow2[i-1] * BASE2 % MOD2; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, q; cin n m q; init_pows(m); vectorint cnt(m, 0); long long h1 0, h2 0; setpairlong long,long long seen; seen.insert({h1, h2}); while (q--) { int type, idx; cin type idx; // idx 是 0-based 的原子状态下标 if (type 1) { int delta 1; // 根据题目定义调整 h1 (h1 delta * pow1[idx]) % MOD1; h2 (h2 delta * pow2[idx]) % MOD2; cnt[idx]; } else if (type 2) { int delta -1; // 同理根据题目定义 h1 (h1 delta * pow1[idx] MOD1) % MOD1; h2 (h2 delta * pow2[idx] MOD2) % MOD2; cnt[idx]--; } pairlong long,long long cur {h1, h2}; if (seen.count(cur)) { cout 重复状态出现 \n; } else { seen.insert(cur); } } return 0; }代码本身的业务细节需要你把原题输入的操作语义套进去但增量哈希的骨架是通用的。唯一要注意的是每次减法取模时要先加上模数再取模避免出现负数。3.3 复杂度分析与数据规模估算这套方案的总复杂度是 $O(n m q)$ 的预处理加查询预计算幂次是 $O(m)$每次操作是 $O(1)$ 的哈希更新加上字典查找。字典如果使用标准库的set单次操作是 $O(\log q)$如果换成unordered_set期望是 $O(1)$但需要自定义哈希函数否则容易被构造数据卡掉。我最终比赛环境里用的是set虽然多一个对数因子但胜在稳定、不会触发哈希碰撞攻击时间上也完全在限制内。我算了一笔账$n$ 和 $m$ 都在 $2 \times 10^5$ 量级所以 $O((nmq)\log q)$ 大概就是几百万次操作在 2 秒时间限制内毫无压力。这正是“用对数换实现稳定性”的典型例子。3.4 初始化状态的一致性陷阱一个特别容易被忽略的细节是初始状态也要放进历史记录里。很多人从第一次操作后的状态才开始记录导致初始状态和后续某个操作结束后的状态重复时无法被识别。我当时第一版就是这么错的样例过了交上去 WA 了一片后来加了一行seen.insert({0, 0})才好了。另一个相关问题是如果原子状态的计数值会加到很大比如超过 $10^9$直接用cnt[idx]做乘法更新哈希时要注意溢出。虽然取模能兜底但中间乘法建议先转成long long再模别在int上做乘法。4. 常见报错与调试实录4.1 样例通过但 WA 的三种高频原因刷题多了你会发现“样例全过、提交全挂”是有规律的。AT_abc417_e 这类题最常见的三种 WA 原因如下状态编码遗漏了某些维度。如果你只是简单地把计数数组直接哈希但某些会影响判定的关键结构没被编入哈希那么两个实际不同的状态就会产生相同的编码导致误判。处理方式是重新审视题目的判定条件确保所有“会影响答案”的信息都进入了哈希。取模出现负数。C 里负数取模的结果是负数如果随后用作数组下标或者判断条件必然出错。所有减法更新都要先加模数再取模。输入数据没读完。操作数一多cin没关同步的话可能超时更隐蔽的是循环边界写错漏读了一行数据导致后续全部错位。我习惯在本地用随机大数据生成器自测能有效避免这类问题。4.2 哈希碰撞导致的不稳定表现虽然双哈希碰撞概率极低但并非零。在比赛环境中如果有人刻意构造攻击数据针对单哈希已知碰撞单哈希会直接挂掉。双哈希的碰撞概率基本低于 $10^{-18}$在实际比赛中完全够用。不过还有一个小点底数的选择也很重要。我们常用的大质数底数比如 $911382323$、$972663749$本身接近 $10^9$模数也是 $10^9$ 级别相乘后需要用long long才能保证安全。如果你实在不放心哈希还有另一个思路用std::mapvectorint, int直接存整个计数数组。但这么做单次操作是 $O(m)$ 的在 $m$ 较大的情况下会超时。所以哈希路线基本是唯一实用的方案。4.3 调试阶段我用过的几个工具性技巧这道题调试起来不算太舒服因为状态空间大肉眼跟踪基本不现实。我分享一下自己排查问题的三板斧先写一个暴力版本。用最朴素的方式维护完整的计数数组每次操作完直接把整个数组打印或者对整个数组做一次哈希作为基准正确答案。把优化版本的输出和暴力版本做 diff一旦不一致就可以二分定位到最早出现差异的一步。用随机数据压测。写一个随机操作生成器生成 $10^4$ 组小规模数据跑暴力版和优化版对比结果。这个步骤能抓出绝大多数逻辑边界问题。加日志输出关键中间状态。在遇到第一个不一致时打印出当前的哈希值、计数数组、操作序列然后手动演算基本就能发现问题。这三板斧不仅适用于这道题几乎所有需要写数据结构的竞赛题都可以用同样策略。磨刀不误砍柴工调试环节多花十分钟可能比你在草稿纸上干想一个小时还管用。4.4 经验清单以后再遇到的同类题的速查表我整理了一个适合“动态状态判定/计数”类题目的速查表下次遇到类似 E 题可以直接照着过一遍要点建议判定数据规模$n 10^4$ 时优先考虑数据结构解法而非暴力枚举状态可压缩性把所有原子状态的频率作为状态是否有可哈希编码增量更新方式能否在 $O(1)$ 或 $O(\log n)$ 内完成状态迁移哈希选择竞赛优先双哈希避免单哈希被构造数据卡掉历史状态记录用 set/unordered_set 维护注意初始状态也要塞进去边界条件减法取模加模数初始化预计算数组输入读完这张表的思路和我在处理这一题时的方法是一致的。刷题到最后比拼的往往不是你会多少高级算法而是能不能快速把一道陌生题目映射到已知的套路框架里。5. 写在最后的个人体会这题给我最大的收获不是双哈希本身而是逼着我重新审视“怎么从题目描述提炼状态”这件事。很多时候我们卡题不是因为代码写不出来而是因为对题目的理解停留在一个过度复杂的层面。AT_abc417_e 如果可以重来一次我会提醒自己先花二十分钟把状态定义想清楚再动手敲代码。如果你现在也卡在这道题上我建议你把样例手动模拟两三组找出每组操作前后状态变化的规律想清楚“什么是不变的、什么是在变的”解法和代码自然会浮出水面。另外刷题归刷题身体和心态还是很重要的。我因为调这题调了太久脑子都糊了后来出门走了走回来再看一眼代码立刻发现了那个漏掉的初始状态插入。这种情况下放松不是懈怠是战术性重启——你也值得试一试。

AT_abc417_e 题解：增量哈希与双哈希高效维护动态状态

相关推荐

具身智能产业化策略（5）：边缘推理与云端推演任务切分策略

大模型上下文管理实战：从context-mode原理到多轮对话优化方案

RSA低加密指数广播攻击实战：从数学原理到AI辅助Writeup

更多资讯

SpringBoot+Netty构建高性能聊天服务实战

context-mode：智能体上下文调度中枢设计与SQLite+FTS5实战

AutoHedge：面向AI工程化的轻量级API服务编排中枢

终极TelegramSwift性能调优指南：7个提升macOS应用响应速度的秘诀

Linux内核模块加载顺序与开机自动加载机制全解

OpenCore Legacy Patcher 完整指南：2007 年的 Mac 也能装上 macOS Sequoia

今日更新

CopilotKit Vue Demo 与 React Demo 的 Parity 实现指南：路由、运行时端点与交互语义的全框架对齐

Harbor RBAC 实战：db_auth 模式下非管理员用户管理项目成员的完整验证与权限模型解析

STM32平衡车纯平衡程序从拆包到参数整定的完整调试指南

本周精选

超人会飞不算本事：系统稳定依赖清晰规则与边界设计

超人VS蜘蛛侠：拆解超级IP的影响力与传播方法论

基于CNN的调制信号识别：MATLAB实现时频图分类实战

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？