Codeforces 2276E — Good Substrings 题解

题目链接：2276E — Good Substrings。 这道题的难点是：确定哪些子串合法之后，怎样一次性把它们的贡献加到每个位置上？ 可以先展开下面的 Tips 自己想一想，再继续看推导。

题意

给定一个长度为 n 的数字字符串 s。 如果一个子串包含子序列 2025，却不包含子序列 2026，它就是坏子串；其余都是好子串。 对每个位置，求包含这个位置的好子串数量。 所有测试用例的长度之和不超过 3 × 10⁵。

注意区分：子串必须连续，子序列可以不连续。 下文字符串下标统一从 0 开始，只有差分数组在实现时转换成 1 下标。

Tips：逐步接近解法

六个提示由浅到深，建议每次只展开一个，先沿着提示继续思考。

Tip 1：先考虑更容易描述的反面

好子串有多种情况，坏子串却只有一种明确的条件。 对位置 k 来说，所有包含它的子串一共有多少个？如果能统计坏子串的贡献，就可以从总数中扣除。

Tip 2：固定左端点，观察右端点的变化

左端点不变，右端点逐渐向右移动。一旦子串中出现了 2025 这个子序列，它还会消失吗？ 对 2026 做相同的观察，想一想坏子串的右端点会组成什么形状的集合。

Tip 3：利用两个模式串的共同部分

2025 和 2026 都以 202 开头。 如果每一步都选最早能匹配的位置，会给后面的字符留下更多还是更少的选择？ 是否有必要分别寻找两遍这个共同前缀？

Tip 4：换一个统计顺序

先别对每个位置枚举覆盖它的子串。反过来，一条合法子串会给它覆盖的每个位置贡献 1。 固定左端点后，能否把一整段右端点对应的子串一起处理？

Tip 5：把一组区间叠起来

写下 [l,l]、[l,l+1]、…、[l,r] 这组子串。 它们在位置 l、l+1、…、r 上分别贡献多少次？ 如果这是一段等差数列，一次差分之后是什么，两次差分之后又是什么？题目只需要最终答案。

Tip 6：让字符查找也做到常数时间

查找过程反复询问的都是“从某个位置开始，数字 d 第一次出现在哪里”。 数字只有 10 种，能否从右往左扫描字符串，一次性预处理所有查询？

固定左端点，找到坏子串的范围

固定左端点 l，依次贪心寻找最早出现的 2 → 0 → 2。 再从最后一个 2 之后，分别寻找最早的 5 和 6，记其位置为 p5、p6。找不到时记为 n。

为什么只需要最早的 202？对于任意一种匹配方案，逐个字符比较，贪心选到的位置都不会更靠后。 因此，任何其他 202 后面能接到的 5 或 6，贪心方案也能接到。 得到的 p5、p6 就是两个模式串最早能够匹配完成的位置。

当右端点 r 满足 r ≥ p5 时，子串包含 2025； 当 r ≥ p6 时，子串包含 2026。 两个条件合起来，坏子串的右端点恰好满足：

p5 ≤ r < p6

• p5 < p6：坏右端点组成区间 [p5, p6 - 1]。
• p5 ≥ p6：不存在坏右端点。
• p6 = n 且 p5 < n：坏右端点一直延伸到字符串末尾。
• 连 202 都找不到时，后续查询都返回 n，于是 p5 = p6 = n。

例如 s = 202516，固定 l = 0，有 p5 = 3、p6 = 5。 坏子串只有 s[0..3] = 2025 和 s[0..4] = 20251； 右端点到达 5 时，子串也包含了 2026，就重新变成好子串。

合并一组子串的贡献

如果逐个坏子串做区间加，子串数量仍然可能达到 O(n²)。 我们需要把固定左端点的一组子串合并。

定义 T(l,r) 为所有子串 [l,l]、[l,l+1]、…、[l,r] 对整个答案数组的总贡献。对于位置 k，它被覆盖的次数是：

T(l,r)[k] = r - k + 1，若 l ≤ k ≤ r；否则为 0。

因为包含位置 k 的右端点可以取 k、k+1、…、r。 所以 T(l,r) 在区间 [l,r] 上是一段递减的等差数列：

r - l + 1，r - l，…，2，1

现在，固定左端点 l 的全部子串贡献就是 T(l,n-1)。 当 p5 < p6 时，坏子串的贡献为：

T(l,p6-1) - T(l,p5-1)

这里相减的是两组子串的覆盖次数：前者包含右端点不超过 p6-1 的全部子串， 后者去掉右端点小于 p5 的部分，剩下的刚好是坏子串。 因此，每个左端点只需要最多三次等差数列更新：

add(l, n - 1, 1);          // 加入所有右端点
if (p5 < p6) {
    add(l, p6 - 1, -1);    // 扣掉右端点不超过 p6 - 1 的子串
    add(l, p5 - 1, 1);     // 把其中尚未出现 2025 的部分加回来
}
  

用 202516 看一遍贡献

对 l = 0，坏子串贡献为 T(0,4) - T(0,2)，也就是 [5,4,3,2,1,0] - [3,2,1,0,0,0] = [2,2,2,2,1,0]。 其他左端点无法再匹配出 2025，因此这个例子的全部坏贡献就只有这些。

样例中每个位置的覆盖次数

下标	0	1	2	3	4	5
字符	2	0	2	5	1	6
全部子串的贡献	6	10	12	12	10	6
坏子串的贡献	2	2	2	2	1	0
好子串的贡献	4	8	10	10	9	6

表中“全部子串的贡献”也可以直接算成 (k+1) × (n-k)： 左端点有 k+1 种选法，右端点有 n-k 种选法。 代码中对每个 l 执行一次 add(l,n-1,1)，累加出的正是这个值，不能再额外加一遍。

二阶差分：为什么只改三个点

剩下的问题是：怎样在 O(1) 时间内实现 add(l,r,v)，给位置 l、l+1、…、r 分别加上 (r-l+1)v、(r-l)v、…、v？

为了与实现一致，这一节把区间端点换成 1 下标： L = l+1、R = r+1。设这次操作产生的贡献数组为 F， 区间内 F[x] = (R-x+1)v，区间外为 0。

因为数列从左往右递减，这里采用反向差分：

D[x] = F[x] - F[x+1]
E[x] = D[x] - D[x+1]

一次差分后，在 [L,R] 内相邻两项只相差 v，所以这一段的 D[x] 全部等于 v。 但左边界前一格还有一个跳变：D[L-1] = -(R-L+1)v。 其余位置为 0。

再差分一次，常数段内部全部抵消，只有三个位置需要修改：

一次等差数列更新在二阶差分数组中的修改

位置	增量	来源
R	+v	常数段右端：v - 0
L-1	-(R-L+2)v	左边界：-(R-L+1)v - v
L-2	+(R-L+1)v	跳变之前：0 - (-(R-L+1)v)

这就是代码里的三个单点修改：

auto add = [&](int l, int r, i64 v) {
    ++l;
    ++r;
    diff[r] += v;
    diff[l - 1] -= (r - l + 2) * v;
    if (l >= 2) {
        diff[l - 2] += (r - l + 1) * v;
    }
};
  

转换后如果 L = 1，L-2 会成为负下标，直接跳过即可。 下标 0 是辅助位置，也不需要恢复或输出；两次后缀和只处理 1..n，这些左侧边界项不会影响有效答案。

恢复方向要与差分定义一致。 我们定义的是 F[x] - F[x+1]，因此要从右向左做后缀和。 第一次恢复一阶差分，第二次恢复最终贡献，不能照搬常见的两次前缀和。

后继数组：让匹配也变成 O(1)

一种直接的实现是记录每个数字出现的位置，再用 lower_bound 查找后继。 每个左端点只查 5 次，但单次查询是 O(log n)，总时间仍是 O(n log n)。 这里数字种类固定，可以直接预处理。

定义 nxt[i][d] 为下标不小于 i 的位置中，数字 d 第一次出现的位置。 不存在时返回 n。从右往左复制下一行，再更新当前数字即可：

std::vector<std::array<int, 10>> nxt(n + 1);
nxt[n].fill(n);
for (int i = n - 1; i >= 0; --i) {
    nxt[i] = nxt[i + 1];
    nxt[i][s[i] - '0'] = i;
}
  

查询时依次跳转 2 → 0 → 2，然后分别查询 5 和 6。 nxt[n] 也被初始化成 n，因此即使中途匹配失败，继续查询也不会越界。

代码查询下一个字符时没有把当前位置加 1，这是因为本题模式串中相邻字符都不同，实际匹配位置自然会严格递增。 如果推广到含有相邻相同字符的模式串，例如 22，就必须从前一次匹配位置的后一位继续查询，并处理越界。

完整代码 · C++17

下面保留“先加入全部子串，再扣掉坏子串”和两次后缀和的实现。 diff 在更新阶段保存二阶差分，恢复后直接作为答案数组使用。

#include <array>
#include <iostream>
#include <string>
#include <vector>

using i64 = long long;

void solve() {
    int n;
    std::string s;
    std::cin >> n >> s;

    // nxt[i][d]：从 i 开始，数字 d 第一次出现的位置。
    std::vector<std::array<int, 10>> nxt(n + 1);
    nxt[n].fill(n);
    for (int i = n - 1; i >= 0; --i) {
        nxt[i] = nxt[i + 1];
        nxt[i][s[i] - '0'] = i;
    }

    auto nextPos = [&](int idx, int digit) {
        return nxt[idx][digit];
    };

    std::vector<i64> diff(n + 2);

    // 对 [l,r] 加上 v*(r-l+1), v*(r-l), ..., v。
    // 参数是 0 下标，函数内部转换为 1 下标。
    auto add = [&](int l, int r, i64 v) {
        ++l;
        ++r;
        diff[r] += v;
        diff[l - 1] -= (r - l + 2) * v;
        if (l >= 2) {
            diff[l - 2] += (r - l + 1) * v;
        }
    };

    for (int l = 0; l < n; ++l) {
        int p2_1 = nextPos(l, 2);
        int p0 = nextPos(p2_1, 0);
        int p2_2 = nextPos(p0, 2);
        int p5 = nextPos(p2_2, 5);
        int p6 = nextPos(p2_2, 6);

        add(l, n - 1, 1);
        if (p5 < p6) {
            add(l, p6 - 1, -1);
            add(l, p5 - 1, 1);
        }
    }

    // 两次后缀和：二阶差分 -> 一阶差分 -> 答案。
    for (int pass = 0; pass < 2; ++pass) {
        for (int i = n; i >= 1; --i) {
            diff[i] += diff[i + 1];
        }
    }

    for (int i = 1; i <= n; ++i) {
        std::cout << diff[i] << " \n"[i == n];
    }
}

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

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
  

复杂度与实现细节

• 时间复杂度 O(n)：后继数组需要 O(10n)，每个左端点做常数次查询与更新，最后两次后缀和需要 O(n)。
• 空间复杂度 O(n)：后继数组占 O(10n)，差分数组占 O(n)。数字种类固定为 10。
• 答案使用 64 位整数：单个位置的答案最多为 (k+1)(n-k)，可能超过 32 位整数范围。
• 无需线段树或树状数组：更新全部完成后才读取答案，离线差分就足够了。

题目需要读取整个字符串，并输出 n 个答案，因此线性时间已经达到渐进时间复杂度的下界。 这个做法中值得复用的是：把“固定一端、另一端落在连续范围内”的子串贡献，拆成两组嵌套区间的贡献之差； 嵌套区间叠加出的等差数列，就可以交给二阶差分处理。

参考

• Codeforces 2276E — Good Substrings：题面与样例
• Educational Codeforces Round 195 官方题解：同样使用后继数组与差分统计贡献，本文采用反向二阶差分展开推导。