ABC455-E 复盘：前缀差值统计与三集合容斥

前言

本题给定一个只由 A、B、C 三种字符组成的字符串 $S$，要求统计有多少个非空子串满足：

子串中 A、B、C 的出现次数两两不同。

设某个子串中三种字符的出现次数分别为 $a,b,c$，那么合法条件为：

$$a,b,c \text{ 两两不同}$$

等价于：

$$a\ne b,\quad b\ne c,\quad c\ne a$$

字符串长度满足：

$$1\le N\le 2\times 10^5$$

因此不能直接枚举所有子串。

---

一、暴力做法的问题

最直接的想法是枚举所有子串 $[l,r]$，再通过前缀和 $O(1)$ 求出其中 A、B、C 的出现次数。

例如预处理：

preA[i] = 前 i 个字符中 A 的出现次数
preB[i] = 前 i 个字符中 B 的出现次数
preC[i] = 前 i 个字符中 C 的出现次数

则子串 $[l,r]$ 中三种字符的出现次数为：

$$a=preA[r]-preA[l-1]$$ $$b=preB[r]-preB[l-1]$$ $$c=preC[r]-preC[l-1]$$

然后判断 $a,b,c$ 是否两两不同。

但是子串数量为：

$$\frac{N(N+1)}{2}$$

当 $N=2\times 10^5$ 时，数量达到 $10^{10}$ 级别，因此 $O(N^2)$ 枚举子串不可行。

本题的关键不在于如何快速求一个子串的字符数量，而在于：

如何不枚举子串，却能统计满足某种数量关系的子串个数。

---

二、反向统计不合法子串

题目要求统计满足：

$$a\ne b,\quad b\ne c,\quad c\ne a$$

的子串。

直接统计两两不同并不方便，因此考虑统计其补集。

不合法子串满足至少一个条件：

$$a=b \quad \text{或} \quad b=c \quad \text{或} \quad c=a$$

于是可以先统计：

• A 数量等于 B 数量的子串个数
• B 数量等于 C 数量的子串个数
• C 数量等于 A 数量的子串个数

然后用总子串数量减去不合法数量。

但是这三个集合之间存在重叠。如果一个子串满足：

$$a=b=c$$

那么它会同时被计入：

• $a=b$
• $b=c$
• $c=a$

也就是被重复统计三次。

而作为“不合法子串”，它本来只应该被统计一次。

因此后续需要使用容斥处理这一部分重复。

---

三、从 $A=B$ 到前缀差值相等

先只考虑一个条件：某个子串中 A 和 B 的数量相等。

定义前缀差值：

$$d_i=preA[i]-preB[i]$$

对于子串 $[l,r]$，若其中 A 和 B 数量相等，则有：

$$preA[r]-preA[l-1]=preB[r]-preB[l-1]$$

移项可得：

$$preA[r]-preB[r]=preA[l-1]-preB[l-1]$$

也就是：

$$d_r=d_{l-1}$$

因此：

子串 $[l,r]$ 中 A 和 B 数量相等，等价于前缀位置 $r$ 与 $l-1$ 的差值 $preA-preB$ 相等。

这样一来，问题就从“枚举子串”转化为“统计相同前缀状态出现了多少次”。

---

四、前缀状态计数

如果从左到右扫描字符串，并维护当前前缀差值 $d$，那么每到一个前缀位置，只需要知道：

之前有多少个前缀位置的差值也等于当前 $d$。

假设当前差值为 $d$，之前已经出现过 mp[d] 次，那么当前前缀位置可以和这些位置分别组成一个满足 A 数量等于 B 数量的子串。

因此新增贡献为：

ans += mp[d];
mp[d]++;

这一步并没有枚举所有左端点，而是用 mp[d] 一次性统计出可行左端点数量。

同理：

• 统计 $a=b$，使用差值 $preA-preB$
• 统计 $b=c$，使用差值 $preB-preC$
• 统计 $c=a$，使用差值 $preC-preA$

代码中分别对应：

int d1 = preA - preB;
tot2 += mpAB[d1]++;

int d2 = preB - preC;
tot2 += mpBC[d2]++;

int d3 = preC - preA;
tot2 += mpCA[d3]++;

其中 tot2 记录的是三个集合大小的总和：

$$tot2=cnt_{AB}+cnt_{BC}+cnt_{CA}$$

---

五、为什么需要统计 $A=B=C$

如果只计算：

$$cnt_{AB}+cnt_{BC}+cnt_{CA}$$

会出现重复。

对于一个满足：

$$a=b=c$$

的子串，它会同时满足：

$$a=b$$ $$b=c$$ $$c=a$$

因此会在 $cnt_{AB}$、$cnt_{BC}$、$cnt_{CA}$ 中各被统计一次，总共被统计三次。

但它作为不合法子串，只应该被统计一次，所以多统计了两次。

设满足 $a=b=c$ 的子串数量为 $cnt_{ABC}$，则不合法子串数量为：

$$bad=cnt_{AB}+cnt_{BC}+cnt_{CA}-2cnt_{ABC}$$

所以最终答案为：

$$ans=total-bad$$

即：

$$ans=total-cnt_{AB}-cnt_{BC}-cnt_{CA}+2cnt_{ABC}$$

代码中写作：

cout << tot - tot2 + tot3 * 2;

其中：

• tot：所有非空子串数量
• tot2：$cnt_{AB}+cnt_{BC}+cnt_{CA}$
• tot3：$cnt_{ABC}$

---

六、二维状态统计 $A=B=C$

接下来需要统计满足：

$$a=b=c$$

的子串数量。

这个条件可以拆成两个条件：

$$a=b$$ $$b=c$$

因此对于前缀状态，可以同时维护两个差值：

$$(preA-preB,\ preB-preC)$$

对于子串 $[l,r]$，如果有：

$$(preA[r]-preB[r],\ preB[r]-preC[r])=(preA[l-1]-preB[l-1],\ preB[l-1]-preC[l-1])$$

那么中间这段子串同时满足：

$$a=b$$

和：

$$b=c$$

于是：

$$a=b=c$$

因此可以用二维状态计数：

tot3 += mpABC[getKey(d1, d2)]++;

这里使用的是：

d1 = preA - preB;
d2 = preB - preC;

只要两个前缀位置的 (d1,d2) 完全相同，它们之间的子串就满足 A=B=C。

---

七、二维状态压缩成 long long

C++ 中 unordered_map<pair<int,int>, long long> 默认不能直接使用，因为标准库没有为 pair<int,int> 提供默认哈希函数。

因此可以将二维状态手动压缩成一个 long long。

代码如下：

constexpr ll offset = 200005, base = 500005;

ll getKey(int x, int y) {
    return 1ll * (x + offset) * base + (y + offset);
}

由于前缀差值范围不会超过：

$$[-N,N]$$

而 $N\le 2\times 10^5$，所以将差值加上 offset 后可以变为非负数。

base 需要大于第二维可能出现的最大值，保证不同的二元组不会被压缩到同一个键值。

可以将这个过程理解为：

用类似进制表示的方法，将二维坐标 $(x,y)$ 编码成一个整数。

即：

$$key=(x+offset)\times base+(y+offset)$$

只要保证：

$$0\le y+offset<base$$

那么这个编码就是唯一的。

---

八、初始化

空前缀也必须计入。

因为一个从第 $1$ 个字符开始的子串 $[1,r]$，对应的前缀端点是：

$$0 \quad \text{和} \quad r$$

所以初始时，各个差值状态都应出现一次：

void init() {
    mpAB[0] = 1;
    mpBC[0] = 1;
    mpCA[0] = 1;
    mpABC[getKey(0, 0)] = 1;
    tot = 1ll * n * (n + 1) / 2;
}

其中：

$$tot=\frac{N(N+1)}{2}$$

表示所有非空子串数量。

从前缀角度看，前缀位置一共有 $N+1$ 个，任意选择两个不同的前缀位置即可确定一个非空子串，因此也可以写成：

$$\binom{N+1}{2}=\frac{N(N+1)}{2}$$

---

九、主循环

扫描字符串时，只需要维护当前前缀中 A、B、C 的数量，不需要保存整个前缀数组。

for (int i = 0; i < n; i++) {
    if (s[i] == 'A') {
        preA++;
    } else if (s[i] == 'B') {
        preB++;
    } else {
        preC++;
    }
    cnt();
}

每次读入一个字符后，更新当前前缀数量，再统计以当前位置作为右端点的新增贡献。

cnt 函数如下：

void cnt() {
    int d1 = preA - preB;
    tot2 += mpAB[d1]++;
    int d2 = preB - preC;
    tot2 += mpBC[d2]++;
    int d3 = preC - preA;
    tot2 += mpCA[d3]++;
    tot3 += mpABC[getKey(d1, d2)]++;
}

这里的核心是：

当前状态之前出现过多少次，就新增多少个以当前位置为右端点的合法配对。

---

十、完整代码及提交记录

点击展开/折叠 最终AC代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll offset = 200005, base = 500005;

int n, preA, preB, preC;
ll tot, tot2, tot3;
string s;
unordered_map<int, ll> mpAB, mpBC, mpCA;
unordered_map<ll, ll> mpABC;

ll getKey(int x, int y) {
    return 1ll * (x + offset) * base + (y + offset);
}

void init() {
    mpAB[0] = 1;
    mpBC[0] = 1;
    mpCA[0] = 1;
    mpABC[getKey(0, 0)] = 1;
    tot = 1ll * n * (n + 1) / 2;
}

void cnt() {
    int d1 = preA - preB;
    tot2 += mpAB[d1]++;
    int d2 = preB - preC;
    tot2 += mpBC[d2]++;
    int d3 = preC - preA;
    tot2 += mpCA[d3]++;
    tot3 += mpABC[getKey(d1, d2)]++;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> s;
    init();

    for (int i = 0; i < n; i++) {
        if (s[i] == 'A') {
            preA++;
        } else if (s[i] == 'B') {
            preB++;
        } else {
            preC++;
        }
        cnt();
    }

    cout << tot - tot2 + tot3 * 2;
    return 0;
}

提交记录如下，可见时间复杂和空间复杂度都比较优秀。

以及一些做题时的草稿:)

---

十一、复杂度分析

扫描字符串一次，每个位置只进行常数次哈希表查询和更新，因此时间复杂度为：

$$O(N)$$

哈希表中存储的前缀状态数量最多为 $O(N)$，因此空间复杂度为：

$$O(N)$$

在本题中：

$$N\le 2\times 10^5$$

因此该复杂度可以通过。

---

结语

这题的关键不在于前缀和本身，而在于将“子串中的字符数量关系”转化为“两个前缀状态相等”。

对于 $a=b$ 这类条件，可以用一维前缀差值统计；对于 $a=b=c$ 这类同时满足两个等式的条件，则需要用二维前缀状态统计。

最后再通过容斥处理三个不合法集合之间的重复计数。

整体思路可以概括为：

1. 用总子串数作为全集
2. 反向统计至少两个字符数量相等的不合法子串
3. 用前缀差值统计三个一维条件
4. 用二维差值统计三者相等的重叠部分
5. 通过容斥得到最终答案

这类题的启发在于：

前缀和不只可以用来快速求区间和，也可以通过“状态相等”来统计满足特定区间关系的数量。