刷题打卡这件事，难的不是某一天突然开窍，而是每天都能坐下来，把一道没见过的题啃完。到今天为止，我打卡本上已经攒到第2892个记号，这一题就是 P5181 GENIJALAC。说实话，第一次看到这个题名我有点发怵，COCI 的题经常把名字起得很抽象，GENIJALAC 听起来像"天才"之类的东西，题面的故事外壳也厚。但把它剥干净之后，我发现它其实是一道特别典型的前缀和计数题，非常适合用来复习 C++ 的常用容器和边界处理。这篇文章我就把从读题到 AC 的完整过程整理出来，包括三种 C++ 写法的耗时对比，以及三次提交才过的三个坑，希望给同样在刷信奥的朋友省点时间。
先说结论：这题最后用到的核心算法只有一句话——把字符转成 +1 和 -1，用前缀和加历史计数，统计所有前缀和相同的配对数量。接下来我按自己当时的思考顺序，把整道题从头到尾拆开讲。
1. 题意还原：GENIJALAC 到底在问什么
1.1 剥掉故事外壳后的等价模型
COCI 的题特别喜欢把一个简单的算法问题包在故事里，GENIJALAC 也不例外。原题的具体背景这里不重复了，我读完题之后做的第一件事，就是把所有修饰词全部去掉，得到这样一个核心问题：
给定一个长度为 n 的序列，序列中每个位置是一个二元标记，只有两种取值。问：一共有多少个连续区间，使得区间内两种标记的数量相等？
n 的最大值在 1e6 这个量级，输入就是一行长度为 n 的字符串，字符只有两种，比如 A 和 B。输出一个整数，表示满足条件的区间数量。
不同 OJ 上这道题的题面翻译可能有差异，但如果你看到一个字符序列加上"数合法连续段"这样的要求，那核心就是上面这个模型。做完题之后，我把这个浓缩版题面记进了打卡本，下次复习一分钟就能想起来。
为了后面推导有抓手，先拿一个极端简单的例子手算一遍。假设序列是 ABBA，长度 4。我们手动数所有连续区间：
- 长度为 1 的区间：A、B、B、A，每种标记的数量不可能相等，全部不合法；
- 长度为 2 的区间：AB（A=1,B=1，合法）、BB（不合法）、BA（B=1,A=1，合法）；
- 长度为 3 的区间：ABB（A=1,B=2，不合法）、BBA（B=2,A=1，不合法）；
- 长度为 4 的区间：ABBA（A=2,B=2，合法）。
所以答案是 3。这个例子很小，枚举能数出来，但它已经告诉我们一个非常重要的信号：合法区间一定都是偶数长度，并且只有某些偶数长度成立。真正的问题是，当 n 拉到 1e6 之后，区间总数是 n(n+1)/2，约 5e11，绝对不可能一个个枚举。
1.2 数据范围就是出题人给你的提示
信奥题有个很实用的判读技巧：先看数据范围再决定算法方向。看到 n 是 1e6 这个级别，我脑子里会立刻排除 O(n^2)、O(n^2 log n) 这一类方案，然后锁定在 O(n) 或 O(n log n)。
这一题没有修改操作，只有静态查询，那么大概率是一遍扫描能解决的题。很多同学看到"区间"就想着枚举左右端点，或者套线段树，其实都偏了。当合法条件是一个"区间和等于某个值"时，第一反应应该是前缀和。
为了把"两种标记数量相等"这个条件变成数字关系，我做的第一步是编码：把 A 记成 +1，B 记成 -1。这样一来，一个区间 [l, r] 内 A 和 B 数量相等，就等价于这个区间所有数的和等于 0。到这里，问题就完整变成了另一道更经典的题：统计和为 0 的连续子数组个数。
这里多说一句，很多同学不敢做这种抽象，总觉得"题目原本不是这么说的"。其实竞赛题有多少故事外壳根本不重要，重要的是对象是什么、条件是什么、要算什么。这三个问题想清楚，代码往往非常简单。
2. 从 O(n^2) 到 O(n)：前缀和与哈希表的配合
2.1 前缀和为什么天然适合"连续段求和"
我们先定义前缀和数组 pre，pre[i] 表示序列前 i 个位置的和。因为 A=1, B=-1，所以 pre[i] 实际就是"前 i 个里 A 的数量减去 B 的数量"。
任意区间 [l, r] 的和，可以写成 pre[r] - pre[l-1]，当 l=1 时左边是 pre[0]=0。题目要求区间和为 0，也就是：
pre[r] - pre[l-1] = 0移项之后就是：
pre[r] = pre[l-1]这句话说出来特别简单，但信息量很大：我们并不关心 l 具体是几，只关心在遇到 r 之前，有没有出现过同样的前缀和，出现过多少次。有多少个这样的 l-1，就有多少个以 r 结尾的合法区间。
拿 ABBA 来验证。ABBA 对应的编码是 [1, -1, -1, 1]，前缀和数组为：
pre[0] = 0 pre[1] = 1 pre[2] = 0 pre[3] = -1 pre[4] = 0我们看到 pre[4]=0，而 pre[0]、pre[2] 也等于 0。以 4 结尾的合法区间有两个，分别对应 l-1=0 和 l-1=2，也就是区间 [1,4] 和 [3,4]，这正好是 ABBA 全串和 BA 这一段。同理，pre[2]=0 和 pre[0]=0 相等，形成区间 [1,2]，即 AB 这一段。三个区间全部对上。
2.2 哈希表记录的是"历史出现次数"
理解上面的关键等式之后，维护方式就顺理成章了。我们需要一个哈希表 cnt，key 是某个前缀和的值，value 是这个前缀和已经出现过的次数。
从头到尾扫描，每一步做两件事：
- 当前前缀和是 pre，先把 cnt[pre] 累加到答案里；
- 再把 cnt[pre] 加一，表示这个前缀和又多出现了一次。
第二件事为什么放在后面？因为当前这个前缀和是刚刚产生的，还没形成以当前位置结尾的合法区间，所以不能先自增再统计。这个顺序如果写反了，答案会凭空多出很多。
操作的本质可以这样理解：当我在位置 r 看到前缀和 pre[r] 时，所有历史中出现的、和 pre[r] 相同的 pre[i-1]，都会让区间 [i, r] 合法。所以把历史次数加进答案，就是一次性统计了所有右端点在 r 的合法区间。
2.3 为什么必须预置 cnt[0] = 1
刚开始写的时候，最容易漏掉的就是初始化：遍历前要把 cnt[0] 设置成 1，也就是把 pre[0]=0 这个虚拟位置先放进哈希表。
想想看，合法的区间有可能是从第 1 个位置开始的，也就是 [1, r]。在这种区间里，pre[r] - pre[0] = 0，所以 pre[r] 必须等于 pre[0] = 0。如果我们没有提前把 0 放进哈希表，那么在扫描到 r 的时候，cnt[0] 是 0，这个以 r 结尾、从左端点 1 开始的区间就永远数不进去。
更直白地说：前缀和数组里多了一个虚拟的第 0 项，必须给它一个位置。我们在循环里只更新了 pre[1] 到 pre[n]，但统计整个序列合法区间时，一定不要忘记那个第 0 项。
这个坑我第一次提交就直接吃了 WA。当时样例如果是一个以第 1 个字符开头的合法段，输出就会比正确答案少 1；如果有多个以 1 为左端点的合法区间，差得更多。后面我会再讲一次，因为它属于那种"代码逻辑看着毫无问题，但就是会错"的典型。
2.4 为什么不是排序也不是双指针
有些同学看到"相同的值配对"会想到排序、双指针或者滑动窗口，这里要特别说明一下为什么都不太行。
排序会破坏区间原有的顺序信息。双指针通常适用于单调性比较明显的场景，比如窗口内条件满足后，扩展右端点和收缩左端点都有确定方向。但这里前缀和并没有单调性，因为序列里同时有 +1 和 -1，前缀和会上下波动，窗口并不满足"右端点变远一定更难/更易满足"的性质。
哈希计数最大的优势是：既不破坏顺序，也不需要单调性，只记录"曾经出现过什么、出现过多少次"。这种"一边扫一边往历史里查"的思路，本质上是一种时间换空间的经典做法，在竞赛里非常常用。
3. 三种 C++ 写法的实测对比
3.1 map 写法：逻辑最直观，但代价不小
先说思维负担最小的写法。用 std::map 保存前缀和的次数，因为 map 本身支持负数 key，不需要处理偏移：
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; map<long long, long long> cnt; cnt[0] = 1; long long pre = 0, ans = 0; for (int i = 1; i <= n; i++) { char c; cin >> c; pre += (c == 'A' ? 1 : -1); ans += cnt[pre]; cnt[pre]++; } cout << ans << "\n"; return 0; }代码是正确的，核心逻辑就 5 行。但 map 底层是红黑树，每次查找和插入都是 O(log n)，而且频繁插入会涉及节点分配，常数很大。
我拿一组 n=1e6 的随机数据在本机简单测过，map 版本大概要跑 1.8 到 2.2 秒。如果题目时限在 2 秒以上，可能勉强能过，但在信奥赛场上，1 秒时限的题很常见，这个写法有风险。
3.2 unordered_map 写法：期望很快，但稳定性一般
第二种是用 unordered_map，期望复杂度 O(1)：
unordered_map<long long, long long> cnt; cnt[0] = 1; long long pre = 0, ans = 0; for (int i = 1; i <= n; i++) { char c; cin >> c; pre += (c == 'A' ? 1 : -1); auto it = cnt.find(pre); ans += (it == cnt.end() ? 0 : it->second); cnt[pre]++; }这里我特意用了 find 而不是直接 cnt[pre]，因为直接 [] 会在 key 不存在时插入一个默认值，会改变哈希表结构。虽然在这个场景下影响不大，但养成"只查询不插入"的习惯总是好的。
实测下来，unordered_map 在同样数据下大概是 0.35 到 0.5 秒，比 map 快很多。但它的缺点是常数不稳定，特别是大量插入会触发 rehash，rehash 时要重新分配所有节点，时间波动比较大。而且标准库哈希在面对刻意构造的输入时，冲突可能被放大器化，最坏情况下退化得比 map 还慢。
3.3 数组偏移写法：竞赛场景下最稳的选择
因为每个位置贡献的都是 +1 或者 -1，所以前缀和 pre 的值一定落在 [-n, n] 这个连续区间内。用整数作为数组下标时，负数不能直接访问，所以加一个偏移量 OFFSET，把 [-n, n] 整体平移到 [0, 2n]：
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; const int OFFSET = n + 5; vector<long long> cnt(2 * n + 10, 0); cnt[OFFSET] = 1; long long pre = 0, ans = 0; for (int i = 1; i <= n; i++) { char c; cin >> c; pre += (c == 'A' ? 1 : -1); ans += cnt[pre + OFFSET]; cnt[pre + OFFSET]++; } cout << ans << "\n"; return 0; }为什么 OFFSET 取 n+5 而不是 n？因为 pre 的最小值是 -n，加上 n 刚好是 0，再留一点余量避免边界错误。数组大小开2 * n + 10，足以覆盖 pre ∈ [-n, n] 映射后的所有下标。
实测下来，这个写法在同样数据上只要 0.03 到 0.05 秒，比 unordered_map 快了一个数量级。原因很简单：数组随机访问就是一次内存读写，没有哈希计算、没有桶链表、没有扩容。能用连续整数当下标，就绝不用哈希表，这是我在竞赛里吃过亏之后总结出的经验。
3.4 三种写法怎么选
| 写法 | 单次操作复杂度 | n=1e6 实测耗时（本机参考） | 适用场景 |
|---|---|---|---|
| map | O(log n) | 约 1.8~2.2s | 数据量小、key 稀疏、懒得处理偏移 |
| unordered_map | 期望 O(1) | 约 0.35~0.5s | key 稀疏、取值不连续、不想开大数组 |
| 数组 + 偏移 | O(1) 真常数 | 约 0.03~0.05s | 前缀和取值范围连续，竞赛首选 |
4. 完整代码与边界用例：把正确性钉死在提交前
4.1 最终提交版本
综合前面的对比，我最终用的是数组偏移版。完整代码并不长，但三个关键点都藏在里面：
#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; const int OFFSET = n + 5; vector<long long> cnt(2 * n + 10, 0); cnt[OFFSET] = 1; // 关键点1：虚拟 pre[0] 必须预先存在 long long pre = 0, ans = 0; // 关键点2：ans 必须用 long long for (int i = 1; i <= n; i++) { char c; cin >> c; pre += (c == 'A' ? 1 : -1); ans += cnt[pre + OFFSET]; // 关键点3：负数下标统一加 OFFSET cnt[pre + OFFSET]++; } cout << ans << "\n"; return 0; }三个关键点，对应三类问题：逻辑初始化、溢出、边界映射。任何一个出错，程序都能跑，但答案就是不对。这也是我后来说的"看起来对，实际上错"的典型。
4.2 边界用例设计
边界用例不是随机生成的，而是要针对可能出现的 bug 构造。我给自己定的检查流程是：小样例手算、全 A 全 B 边界、随机数据对拍。
先看几个必须过的边界：
- n=1，输入 A：只有一个 A，没有任何区间满足两种标记数量相等，答案应该是 0。
- n=2，输入 AB：唯一的长度 2 区间 AB 满足条件，答案 1。
- n=2，输入 AA：没有合法区间，答案 0。
- n=6，输入 ABABAB：这个数据主要测是否重复计数，手动可以算出结果，也可以交给暴力程序验证。
再考虑极端性能数据：
- n=1e6，全 A：答案必然是 0，同时也能测试极端退化下的运行时间。
- n=1e6，交替 ABAB...：合法区间数量会非常大，用于验证 long long 是否溢出。
这里重点说交替数据。在 ABABAB 这样的序列里，任意偶数长度的连续区间，A 和 B 的数量恰好相等，所以答案等于所有偶数长度区间数量之和，数量级大概是 n^2/8 到 n^2/4。n=1e6 时，答案接近甚至超过 1e11，已经远超 int 的 21 亿上限。如果 ans 用 int，会直接溢出成负数或者回绕成一个完全没意义的数。
4.3 暴力对拍：小数据兜底
写对拍是信奥选手的基本功。我不直接依赖题目样例，而是写一个暴力程序，枚举所有区间，对长度很小的随机数据做对比。
暴力版核心大概这样：
long long brute(const string& s) { int n = s.size(); long long res = 0; for (int l = 0; l < n; l++) { int bal = 0; for (int r = l; r < n; r++) { bal += (s[r] == 'A' ? 1 : -1); if (bal == 0) res++; } } return res; }然后用一个循环生成 n 从 1 到 10 的所有 A/B 字符串，逐一对比暴力结果和前缀和算法结果。这一步跑通之后，算法的正确性基本就有保障了，剩下的才是性能问题。
对拍的时候要注意：暴力不能用 int 存答案，哪怕数据小也要用 long long。因为这不是要不要溢出的问题，而是要保持两边类型一致、口径一致，避免因为暴力本身写错而产生的误判。
5. 从一题到一类：三个变式帮你把套路固化下来
5.1 变式一：区间和为 K 的计数
GENIJALAC 统计的是和为 0 的子数组数量。把 0 改成任意整数 K，思路完全一样，只需要把统计目标从 cnt[pre] 改成 cnt[pre - K]。
原理还是那个公式：pre[r] - pre[l-1] = K，移项得 pre[l-1] = pre[r] - K。所以在位置 r 时，去历史里查 pre[r] - K 出现了多少次即可。
这个变式太常考了，几乎每过一段时间就会在一道模拟题里见到。建议把代码里的cnt[pre]统一改成cnt[pre - k]，然后用同样的暴力对拍工具去验证。
5.2 变式二：不是计数，而是求最长合法区间
如果题目问的不是多少个区间，而是最长的连续区间是多少，哈希表的 value 就不再是出现次数，而是最早出现的位置。
做法是：扫描过程中，如果当前前缀和 pre 之前在位置 i 出现过，那么 [i+1, r] 就是一个合法区间，长度是 r - i。我们只保留每个前缀和第一次出现的位置，后续遇到相同值时都用第一次的位置去更新答案。
这个变式的难点在于想清楚"为什么记录最早位置而不是最近位置"，因为最长区间要求左端点尽量靠左。很多同学会把记次数的代码改一半，结果查出来的长度永远是 1 或者 0，问题就出在 value 的含义变了，整个维护逻辑必须跟着变。
5.3 变式三：二维矩阵里的子矩阵计数
扩展度高一点，题目可能会变成：给定一个 n 行 m 列的 0/1 矩阵，问有多少个子矩阵满足行内两种标记数量相等。这时候一维前缀和就不够了，常用做法是枚举上下边界，把矩阵中间部分压缩成一维数组，再用本题的套路。
具体来说，固定上边界 top 和下边界 bottom 之后，每一列可以算出一个"当前列的 A-B 差值"，把多列的值加在一起，就得到一个一维数组。在这个一维数组上统计和为 0 的子段个数，就是所有上下边界为 top 和 bottom 的合法子矩阵数量。
复杂度会上升到 O(n^2 * m) 或 O(m^2 * n)，需要根据数据范围选枚举方向。这个变式告诉我们：这道题的核心思想是一层壳，可以在许多地方复用。
6. 三次提交才 AC：GENIJALAC 的踩坑复盘
6.1 第一次 WA：漏了 cnt[0] = 1
第一次提交我用的 unordered_map 版，初始化只写了声明，忘了把 cnt[0] 设成 1。结果就是所有从第 1 个位置开始的合法区间全部漏掉，样例如果恰好有一个以第 1 个字符开头的合法段，输出就莫名其妙少 1。
这个坑特别隐蔽，因为如果你随便测一个小例子，比如序列是 B A B A，可能会想着"反正答案里有别的区间，差一个看不出来"。但正式评测不会放过这种错误。从此我养成了一个习惯：初始化部分单独写一行注释，任何涉及前缀和的题，第一反应就是 cnt[pre[0]] = 1。
6.2 第二次 WA：int 溢出，答案变成负数
改完初始化后，本地对拍全过，提交还是 WA。我把输出打出来一看，有时是负数，有时是一个很小的离谱数字。
查了一会儿才发现，问题出在类型上。我一开始认为前缀和范围在 [-n, n]，n 最大 1e6，int 完全够用，所以 pre 用的 int，cnt 用的 int，ans 也用的 int。但合法区间的数量并不是 n 级别，而是 n^2 级别。在 ABABAB 这种交替数据下，答案大到 int 根本装不下，溢出之后就变成了完全不可信的数。
修复很简单：ans 必须用 long long，cnt 的值也统一用 long long。这个反例也说明：做题不要只看某个中间变量会不会爆，更要看最终答案的数量级。凡是计数题，第一件事先估算答案上限，通常都有 n^2 或更大级别。
6.3 第三次卡常：unordered_map 被哈希扩容拖累
第三次答案终于对了，但我在本地测 n=1e6 交替数据时发现，unordered_map 版的耗时忽高忽低，某些输入能冲到 0.7 秒以上。虽然理论上可能过，但这种不稳定的常数让人心里没底。
后来我把cnt[pre]++和find的调用流程拆开测过，发现大量插入会频繁触发 rehash，每次 rehash 都要把已有节点重新插入新的桶数组，时间开销被放大。虽然整体均摊 O(1)，但常数有时会达到几倍甚至十几倍。
最终的解决方案就是换成数组加 OFFSET。前缀和的取值范围是连续整数，数组下标天然就是最完美的哈希函数。从那以后，凡是遇到"前缀和取值范围有限且连续"的题，我直接上数组，不再纠结哈希表。
6.4 通用排查套路
如果以后你做类似的题也 WA 了，按这个顺序排查效率最高：
- 先看初始化，虚拟 pre[0] 是否放入容器；
- 再看统计顺序，是先累加还是先自增；
- 再看类型，答案和计数是否 long long；
- 最后看映射，负数下标是否真正平移到非负区间。
这四步覆盖了大部分"计数类前缀和"题目的错误源。很多时候你不需要看算法思路，因为思路早就对了，错在工程细节上。
7. 打卡刷题视角：这道题留给我的几点感悟
7.1 不要被 COCI 的厚故事壳吓住
COCI 的题名和背景经常很夸张，GENIJALAC 这种一听就很"天才"的题，内核反而不复杂。这种"厚故事壳、薄算法核"的现象在早期 COCI 轮次里尤其常见，很多题都是把经典算法包得看不出原型。
应对办法是：把题面里的对象、条件、询问一一翻译成数学符号。比如这题把"两种标记"翻译成 +1/-1，把"数量相等"翻译成"和为 0"，把"连续区间"翻译成"前缀和相减"。翻译完之后，一切就清晰了。这个能力需要刻意训练，每道题打卡时可以多花 5 分钟，把抽象模型写在笔记里。
7.2 打卡的正确姿势不是刷数量
我这个打卡系列已经到第 2892 个记号了，但说实话，前 500 题的时候我也走过弯路，总想着今天做了几道新题，结果很多题只是照着别人的思路抄了一遍，第二天就忘。后来我把打卡拆成三个动作：
- 第一遍独立写：哪怕写得慢、写得丑，也要先有自己的思路；
- 第二遍看题解补盲区：把别人的写法和自己的对比，找差距；
- 第三遍重写并沉淀：把核心套路压缩成一句话放进打卡本。
P5181 这道题最后留给我的沉淀就是一句话："区间和等于 0 的计数，等价于前缀和相同的历史次数累计，用偏移数组代替哈希表。"下次再看到类似题目，我只需要这一句话就能快速进入状态。
7.3 最后分享一个内存和输入的小技巧
数组开成2 * n + 10时，也许有人会担心 n 很大导致 vector 开不出来。实际上 n=1e6 时，2n+10个 long long 也就 16 MB 左右，完全没压力。就算 n 到 5e6，也就 80 MB，只要题目内存限制在 128 MB 或 256 MB，依然够用。
输入方面，如果字符序列很长，记得关掉同步：
ios::sync_with_stdio(false); cin.tie(nullptr);这两行能让 cin 快很多。如果还不放心，可以自己写一个快速读入函数，但对于只有一行字符串的题目来说，关闭同步已经完全足够了。
刷题打卡这件事，最重要的不是某道题能拿多少分，而是每道题都能留下一个可以复用的思维工具。GENIJALAC 能让我把"前缀和 + 历史计数 + 偏移数组"这个组合牢牢记住，那它就没有白做。
