AtCoder Beginner Contest 452 题解

for-each2026年8月18日大约 19 分钟

AtCoder Beginner Contest 452 题解

项目	内容
比赛时间	2026-04-04
比赛链接	https://atcoder.jp/contests/abc452
题目数量	A–G 共 7 题

比赛概览

本场整体难度偏向中低，前四题（A–D）基本是入门与基础算法题：A、B 是直接的模拟/构造，C 考察"预处理 + 逐位判断"，D 是一道经典的子序列匹配 DP。E 是一道考察调和级数分组 + 前缀和的数论求和题，思路巧妙值得重点掌握。F 将滑动窗口与树状数组结合求"恰好等于 K 的逆序区间数"，是双指针 + 数据结构的典型训练题。G 是本场区分度最高的一题，需要游程编码 + 后缀数组的高阶技巧，建议量力而行。

A - Gothec

题目链接：https://atcoder.jp/contests/abc452/tasks/abc452_a

题目大意

一年中有五个"季节节日"（五节句）：1 月 7 日、3 月 3 日、5 月 5 日、7 月 7 日、9 月 9 日。给定月份 $M$ 和日期 $D$ ，判断该日期是否为其中之一，是则输出 Yes，否则输出 No。输入保证 $(M,D)$ 是闰年公历中的合法日期。

思路

本题是纯条件判断。五个节日对应的 $(M,D)$ 分别是 $(1,7)$ 、 $(3,3)$ 、 $(5,5)$ 、 $(7,7)$ 、 $(9,9)$ ，直接逐一对 $(M,D)$ 做相等比较即可。

也可以把五个日期放进一个列表/集合，用 (M,D) 是否在列表中判断，逻辑更清晰且不易漏写。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int m, d;
    cin >> m >> d;
    if ((m == 1 && d == 7) || (m == 3 && d == 3) || (m == 5 && d == 5) ||
        (m == 7 && d == 7) || (m == 9 && d == 9)) {
        cout << "Yes\n";
    } else {
        cout << "No\n";
    }
    return 0;
}

官方题解提供的 Python 写法如下：

m, d = map(int, input().split())
gossekulist = [(1, 7), (3, 3), (5, 5), (7, 7), (9, 9)]
print("Yes" if (m, d) in gossekulist else "No")

复杂度分析

时间复杂度： $O(1)$
空间复杂度： $O(1)$

B - Draw Frame

题目链接：https://atcoder.jp/contests/abc452/tasks/abc452_b

题目大意

有一个 $H \times W$ （ $3 \le H, W \le 10$ ）的网格。定义"边界格子"为：与其边相邻的格子数至多为 3 的格子（即上、下、左、右四个方向中至少缺一个邻居）。将边界格子涂黑（#），其余格子涂白（.），输出涂色后的网格。

思路

关键观察：在一个 $H \times W$ 的网格中，普通格子有 4 个边相邻邻居，边上的格子（非角落）有 3 个，角落格子有 2 个。因此"相邻格子数 $\le 3$ "当且仅当该格子位于第一行、最后一行、第一列或最后一列，即满足

i = 1 \;\text{或}\; i = H \;\text{或}\; j = 1 \;\text{或}\; j = W.

（注意：只有当 $H,W \ge 3$ 时这个等价关系才成立，比如 $H=2$ 时所有格子都在边界上；本题约束保证了 $H,W \ge 3$ ，因此可以直接使用上述条件。）

于是输出就是"画一个边框"：第 1 行和第 $H$ 行全为 #，其余行的第 1 列和第 $W$ 列为 #、中间为 .。对每个格子 $O(1)$ 判断并输出即可。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int H, W;
    cin >> H >> W;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (i == 0 || i == H - 1 || j == 0 || j == W - 1) cout << '#';
            else cout << '.';
        }
        cout << '\n';
    }
    return 0;
}

官方题解中给出的 Python 代码缩进有误（每输出一个字符就换行），这里给出修正后的版本：

H, W = map(int, input().split())
for i in range(H):
    for j in range(W):
        if i == 0 or i == H - 1 or j == 0 or j == W - 1:
            print('#', end='')
        else:
            print('.', end='')
    print()

复杂度分析

时间复杂度： $O(HW)$
空间复杂度： $O(1)$

C - Fishbones

题目链接：https://atcoder.jp/contests/abc452/tasks/abc452_c

题目大意

有一个由 1 根脊柱和 $N$ 根肋骨组成的鱼骨架（ $1 \le N \le 10$ ）。脊柱上要写一个长度为 $N$ 的字符串；第 $i$ 根肋骨上要写一个长度为 $A_i$ 的字符串，并且该字符串的第 $B_i$ 个字符必须等于脊柱字符串的第 $i$ 个字符。所有 $N+1$ 个字符串都必须从给定的 $M$ 个互不相同的候选串 $S_1,\dots,S_M$ （长度 $1\le|S_j|\le10$ ， $M\le 2\times10^5$ ）中选取，可重复使用。对每个 $S_j$ ，回答：是否存在一种合法的赋值方式，使得脊柱字符串恰为 $S_j$ 。

思路

关键观察：脊柱上的第 $i$ 个字符会"固定"第 $i$ 根肋骨的一个约束——存在一个候选串，其长度为 $A_i$ 且第 $B_i$ 个字符等于该字符。而每根肋骨的选择彼此独立（候选串可重复使用），因此所有 $N$ 个约束可以同时满足，当且仅当每个约束单独可以满足。

于是对每个候选串 $S_j$ ：

若 $|S_j| \ne N$ ，脊柱长度必须是 $N$ ，直接回答 No；
否则对每个位置 $i = 1,\dots,N$ ，检查"是否存在长度为 $A_i$ 且第 $B_i$ 个字符为 $S_j[i]$ 的候选串"。全部满足则输出 Yes，否则 No。

预处理：直接对每个 $(i, S_j)$ 逐一扫描候选串是 $O(M^2)$ 的，会超时。但候选串长度至多为 10、字符集只有 26 个小写字母，信息量很小。定义布尔数组

\mathrm{memo}[\mathrm{len}][\mathrm{pos}][c] = \begin{cases}\mathrm{True}, & \text{存在长度为 }\mathrm{len}\text{、第 }\mathrm{pos}\text{ 个字符为 }c\text{ 的候选串}\\ \mathrm{False}, & \text{否则}\end{cases}

（ $\mathrm{pos}$ 用 0-indexed 表示）。扫描一遍所有候选串，对每个串的每个字符打标记即可完成预处理。之后每个位置的判断就是 $O(1)$ 查表。

为什么正确：第 $i$ 根肋骨的候选串只通过三元组 $(A_i, B_i, S_j[i])$ 与脊柱交互，且不同肋骨互不干扰。所以"逐位置可行"⟺"整体可行"，不需要搜索组合方式。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<int> A(N), B(N);
    for (int i = 0; i < N; i++) cin >> A[i] >> B[i];
    int M;
    cin >> M;
    vector<string> S(M);
    for (int i = 0; i < M; i++) cin >> S[i];

    // memo[len][pos][c]: is there a candidate string of length len
    // whose pos-th character (0-indexed) is ('a'+c)?
    bool memo[11][11][26] = {};
    for (const auto& s : S) {
        int len = (int)s.size();
        for (int i = 0; i < len; i++) memo[len][i][s[i] - 'a'] = true;
    }

    for (const auto& s : S) {
        if ((int)s.size() != N) { cout << "No\n"; continue; }
        bool ok = true;
        for (int i = 0; i < N; i++) {
            if (!memo[A[i]][B[i] - 1][s[i] - 'a']) { ok = false; break; }
        }
        cout << (ok ? "Yes" : "No") << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度：预处理 $O(M \cdot L + L^2\sigma)$ ，其中 $L = \max |S_j| \le 10$ ， $\sigma = 26$ ；查询每串 $O(N)$ ，总计 $O(MN)$ 。由于 $N, L \le 10$ ，整体为 $O(MN)$ 。
空间复杂度： $O(L^2 \sigma)$ ，即常量级。

D - No-Subsequence Substring

题目链接：https://atcoder.jp/contests/abc452/tasks/abc452_d

题目大意

给定字符串 $S$ （ $1\le|S|\le 2\times10^5$ ）和 $T$ （ $1\le|T|\le50$ ）。统计 $S$ 的非空子串中，不包含 $T$ 作为（不要求连续的）子序列的个数。两个取自不同位置的子串即使内容相同也视为不同。

思路

关键观察：对任意字符串 $X$ ，定义

g(X) = \max\{j \mid T_1T_2\cdots T_j \text{ 是 } X \text{ 的子序列}\}

即 $X$ 所能匹配到的 $T$ 的最长前缀长度。那么" $X$ 不含完整 $T$ 作为子序列" ⟺ $g(X) < |T|$ 。

进一步地， $g$ 的变化规律非常简单。设 $X = Y + c$ （ $c$ 为追加的单个字符），且 $g(Y) = h$ ：

若 $h = |T|$ ： $g(X) = |T|$ （完整 $T$ 仍是子序列）；
若 $h < |T|$ 且 $c = T_{h+1}$ ： $g(X) = h + 1$ ；
否则： $g(X) = h$ 。

为什么 $g$ 至多增加 1？因为若 $T_1\cdots T_j$ 是 $X$ 的子序列且 $j > h+1$ ，则 $T_1\cdots T_{j-1}$ 必是 $Y$ 的子序列（ $T_j$ 要么落在 $Y$ 里，要么用掉最后一个字符 $c$ ），这与 $g(Y) = h < j-1$ 矛盾。

DP 设计：从左到右扫描 $S$ ，维护数组 $dp[j]$ （ $0\le j\le|T|$ ）表示以当前位置结尾的、 $g=j$ 的非空子串个数，并额外用"空子串"作为每个新子串的起点状态。处理字符 $c$ 时：

dp[0]++：表示开启一个新的（当前为空的）子串，起点为当前位置；
对 $j$ 从 $|T|-1$ 递减到 $0$ ：若 $T_j = c$ （0-indexed，即 1-indexed 的 $T_{j+1}$ ），则执行

dp[j+1] \mathrel{+}= dp[j],\qquad dp[j] = 0,

表示把匹配长度从 $j$ 推到 $j+1$ ；若 $T_j \ne c$ ，则 $dp[j]$ 保持不动（追加该字符不改变匹配长度）。
3. 累加答案 $\displaystyle\sum_{j=0}^{|T|-1} dp[j]$ ，即所有以当前位置结尾、 $g < |T|$ （不含完整 $T$ ）的子串数。

注意两点：

必须按递减顺序更新：同一个字符 $c$ 只能让匹配长度增加 1，若按递增顺序更新，一个 $dp[j]$ 会被同一字符连续推移多次，产生错误；
dp[|T|] 从不被清零：已经包含完整 $T$ 的子串，追加任何字符后仍包含完整 $T$ ， $g$ 恒为 $|T|$ ，它们在更新中自然"滞留"在 dp[|T|]。

等价做法：全部非空子串数为 $\dfrac{|S|(|S|+1)}{2}$ ，减去 $\sum_i dp_i[|T|]$ （含完整 $T$ 的子串数）即得答案，两种统计方式完全等价。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string S, T;
    cin >> S >> T;
    int m = (int)T.size();
    vector<long long> dp(m + 1, 0);
    long long ans = 0;
    for (char c : S) {
        dp[0]++;  // start a new (empty) substring before appending c
        // extend existing substrings by appending c (descending to avoid reuse)
        for (int j = m - 1; j >= 0; j--) {
            if (T[j] == c) {
                dp[j + 1] += dp[j];
                dp[j] = 0;
            }
        }
        // substrings ending here that do NOT contain the whole T
        for (int j = 0; j < m; j++) ans += dp[j];
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(|S| \cdot |T|) \approx 10^7$ ，可以轻松通过
空间复杂度： $O(|T|)$

E - You WILL Like Sigma Problem

题目链接：https://atcoder.jp/contests/abc452/tasks/abc452_e

题目大意

给定正整数序列 $A = (A_1,\dots,A_N)$ 和 $B = (B_1,\dots,B_M)$ （ $N, M \le 5\times10^5$ ，元素 $\le 5\times10^5$ ），求

\sum_{i=1}^{N}\sum_{j=1}^{M} A_i \cdot B_j \cdot (i \bmod j) \pmod{998244353}.

思路

直接枚举 $i,j$ 是 $O(NM)$ 的，必然超时。需要利用取模的结构。

关键转化：把求和对 $j$ 单独提出：

\sum_{j=1}^{M} B_j \cdot \sum_{i=1}^{N} A_i \cdot (i \bmod j).

对固定的 $j$ ，按商 $k = \left\lfloor \dfrac{i}{j} \right\rfloor$ 把 $i$ 分组：满足 $\lfloor i/j \rfloor = k$ 的 $i$ 恰好构成区间

jk \le i \le \min\bigl(j(k+1)-1,\; N\bigr),

并且在该区间内 $i \bmod j = i - jk$ 。于是每组对总和的贡献为

B_j \sum_{i \in [l, r]} A_i (i - jk) = B_j \cdot \sum_{i\in[l,r]} A_i \cdot i \;-\; B_j \cdot jk \cdot \sum_{i\in[l,r]} A_i.

前缀和加速：预处理两个前缀和

S_1[t] = \sum_{i\le t} A_i, \qquad S_2[t] = \sum_{i\le t} A_i \cdot i.

则任意区间 $[l, r]$ 上的 $\sum A_i$ 与 $\sum A_i\cdot i$ 都能 $O(1)$ 求出。

复杂度来源：对固定的 $j$ ， $k$ 的取值范围是 $0 \le k \le \lfloor N/j \rfloor$ ，所以总的分组数为

\sum_{j=1}^{M} \left\lfloor \frac{N}{j} \right\rfloor = O(N \log N)

（调和级数 $\frac{N}{1}+\frac{N}{2}+\cdots+\frac{N}{N}$ 的量级），每组 $O(1)$ 计算，总复杂度 $O(N\log N + M)$ ，足够快。

注意事项：全程在模 $998244353$ 下运算，前缀和与中间结果取模，减法时要加模数防止负数。

参考代码

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, M;
    cin >> N >> M;
    vector<long long> A(N + 1), B(M + 1);
    for (int i = 1; i <= N; i++) cin >> A[i];
    for (int i = 1; i <= M; i++) cin >> B[i];

    // prefix sums: sumA[i] = sum A[1..i], sumAi[i] = sum A[k]*k (1 <= k <= i)
    vector<long long> sumA(N + 1, 0), sumAi(N + 1, 0);
    for (int i = 1; i <= N; i++) {
        sumA[i] = (sumA[i - 1] + A[i]) % MOD;
        sumAi[i] = (sumAi[i - 1] + A[i] * i) % MOD;
    }

    long long ans = 0;
    for (int j = 1; j <= M; j++) {
        long long cur = 0;
        // i in [j*k, min(j*(k+1)-1, N)] satisfies i mod j = i - j*k
        for (int k = 0; (long long)k * j <= N; k++) {
            int l = k * j;
            int r = (int)min((long long)(k + 1) * j - 1, (long long)N);
            long long s2 = (sumAi[r] - sumAi[l] + MOD) % MOD;   // sum A_i * i
            long long s1 = (sumA[r] - sumA[l] + MOD) % MOD;     // sum A_i
            cur = (cur + s2 - s1 * (long long)(k * j) % MOD + MOD) % MOD;
        }
        ans = (ans + cur * B[j]) % MOD;
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(N \log N + M)$
空间复杂度： $O(N + M)$

F - Interval Inversion Count

题目链接：https://atcoder.jp/contests/abc452/tasks/abc452_f

题目大意

给定 $1\sim N$ 的一个排列 $P = (P_1,\dots,P_N)$ （ $N\le5\times10^5$ ）和整数 $K$ 。统计满足 $1\le l\le r\le N$ 且子段 $(P_l,\dots,P_r)$ 的逆序对数恰好等于 $K$ 的区间 $(l,r)$ 的个数。

思路

先转化为"不超过"：设 $f(k)$ 为逆序对数不超过 $k$ 的区间个数，则答案

f(K) - f(K-1)

恰好是逆序对数等于 $K$ 的区间数。于是只需高效计算 $f(k)$ 。

单调性观察：

固定左端点 $l$ ，随着 $r$ 增大（在末尾追加元素），逆序对数单调不降；
固定 $r$ ，左端点 $l$ 增大（删除最左元素），逆序对数单调不增。

因此对每个 $l$ ，满足 $\mathrm{inv}(P_l,\dots,P_r) \le K$ 的 $r$ 构成一个从 $l$ 开始的连续区间，且随着 $l$ 增大， $r$ 的右边界也不会回退——这正好可以用**滑动窗口（双指针）**处理。

窗口维护：用树状数组（Fenwick Tree）维护当前窗口 $[l, r)$ 内各值的出现次数：

把 $P_r$ 加入窗口时，新增的逆序对数量等于窗口内比 $P_r$ 大的元素个数，即 $\mathrm{BIT}.\mathrm{sum}(P_r, N)$ （值域是 $[0,N)$ ，因为 $P$ 是排列元素互异，不会算到自己）；
把 $P_l$ 移出窗口时，减少的逆序对数量等于窗口内比 $P_l$ 小的元素个数，即 $\mathrm{BIT}.\mathrm{sum}(0, P_l)$ 。

算法：对每个 $l$ ，先用 while 尽可能把 $r$ 右移（保证加入后逆序对数仍不超过 $K$ ），然后该 $l$ 对答案的贡献是 $r - l$ （即 $r' = l, l+1, \dots, r-1$ 都是合法的右端点），最后把 $P_l$ 移出窗口继续。

为什么贡献是 $r-l$ 而不是 $r-l+1$ ：窗口内当前有效的右端点是 $r' < r$ （最后一个已成功加入的下标是 $r-1$ ），共有 $r-l$ 个； $r$ 本身尚未加入。

边界情况： $K = 0$ 时 $f(K-1) = f(-1) = 0$ ，直接返回 0。 $K$ 最大可达 $\frac{N(N-1)}{2}$ ，需要用 64 位整数。

参考代码

#include <bits/stdc++.h>
using namespace std;

struct BIT {
    int n;
    vector<int> bit;
    BIT(int n) : n(n), bit(n + 1, 0) {}
    void add(int idx, int val) {
        for (int i = idx + 1; i <= n; i += i & -i) bit[i] += val;
    }
    int sumPrefix(int idx) {  // sum over [0, idx)
        int s = 0;
        for (int i = idx; i > 0; i -= i & -i) s += bit[i];
        return s;
    }
    int sum(int l, int r) {   // sum over [l, r)
        return sumPrefix(r) - sumPrefix(l);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    long long K;
    cin >> N >> K;
    vector<int> P(N);
    for (int i = 0; i < N; i++) {
        cin >> P[i];
        P[i]--;  // 0-indexed value
    }

    auto count_leq = [&](long long K) -> long long {
        if (K < 0) return 0;
        BIT bit(N);
        long long now = 0;  // inversion number of window [l, r)
        long long res = 0;
        int r = 0;
        for (int l = 0; l < N; l++) {
            if (r < l) r = l;
            while (r < N && now + bit.sum(P[r], N) <= K) {
                now += bit.sum(P[r], N);  // # elements in window > P[r]
                bit.add(P[r], 1);
                r++;
            }
            res += r - l;   // all windows [l, r') with l <= r' < r
            now -= bit.sum(0, P[l]);  // # elements in window < P[l]
            bit.add(P[l], -1);
        }
        return res;
    };

    cout << count_leq(K) - count_leq(K - 1) << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(N \log N)$ （两次滑动窗口，每次窗口内每个元素进出一次，每次树状数组操作 $O(\log N)$ ）
空间复杂度： $O(N)$

G - 221 Substring

题目链接：https://atcoder.jp/contests/abc452/tasks/abc452_g

题目大意

称一个正整数序列 $X = (X_1,\dots,X_n)$ 为 221 序列，若它的游程编码中每一段"极大连续相等段"的长度恰好等于该段的值。例如 $(2,2,3,3,3,1,2,2)$ 是 221 序列，而 $(1,1)$ 和 $(4,4,1,4,4)$ 不是。给定长度为 $N$ （ $N\le5\times10^5$ ）、元素 $1\le A_i\le 9$ 的序列 $A$ ，统计 $A$ 的连续子段中出现的互不相同的 221 序列的个数。

思路

本题要同时处理两件麻烦事：子段要连续、序列要按"值去重"。官方做法分三步走。

第一步：游程编码与可行性刻画

对 $A$ 做游程编码 $(v_1, m_1),\dots,(v_n,m_n)$ ，其中 $m_i$ 是值 $v_i$ 连续出现的长度。设一个连续子段对应的游程区间为 $[l, r]$ （可能取到首尾块的子段），则该子段是 221 序列当且仅当：

中间块 $l < i < r$ 必须完整取用，因此 $v_i = m_i$ ；
首块 $l$ 、末块 $r$ 只取其中 $v_l$ 、 $v_r$ 个元素，因此只需 $v_l \le m_l$ 、 $v_r \le m_r$ 。

$v_i > m_i$ 的块无论作首、中、尾都不可能出现在 221 子段中，是绝对的"屏障"。

第二步：构造序列 $T$ 并建立一一对应

把游程区间划分成若干个"极大可用块" $[l, r)$ ：块内除首、尾两个块外，中间全部满足 $v_i = m_i$ ；首、尾块只需 $v_i \le m_i$ ；块与块之间必然隔着 $v_i > m_i$ 的屏障。划分方式是扫描游程：遇到 $v>m$ 直接跳过；遇到 $v\le m$ 开始一个块，向右扩展——遇到 $v=m$ 则纳入继续，遇到 $v<m$ 则把它作为当前块的尾块并停止（它同时作为下一个块的起点）。

构造整数序列 $T$ ：先放一个 $0$ ，然后对每个极大可用块，把块内各游程块的值 $v_l,\dots,v_{r-1}$ 依次写入 $T$ ，块结束追加一个 $0$ 作为分隔符。值 $0$ 在这里充当"障碍符"。

关键性质： $T$ 中不含 $0$ 的子数组（值序列）与 $A$ 的 221 子段一一对应。具体地， $T$ 中一段值序列 $(v_a,\dots,v_b)$ 对应 $A$ 的子段：取游程块 $a$ 最右侧的 $v_a$ 个元素、中间块全部、游程块 $b$ 最左侧的 $v_b$ 个元素——它们恰好拼成一个连续子段，且每段长度等于值，因而是 221 序列；反过来任何 221 子段显然落在这段构造内。因此原问题转化为：统计 $T$ 中不含 $0$ 的互异子数组个数。

第三步：用后缀数组统计互异子数组

设 $T$ 的长度为 $M$ 。记后缀数组为 $\mathrm{sa}$ ， $\mathrm{lcp}[i]$ 为字典序第 $i-1$ 与第 $i$ 个后缀的最长公共前缀长度。再预处理

\mathrm{zf}[p] = \text{从位置 }p\text{ 起连续不含 }0\text{ 的字符个数}.

按字典序依次考察每个后缀。对排名 $i$ 的后缀（起点 $p = \mathrm{sa}[i]$ ）：任何以 $p$ 为起点的子数组都是该后缀的前缀。其中长度不超过 $\mathrm{lcp}[i-1]$ 的前缀，已经在排名更靠前的后缀中出现过（后缀数组的相邻性质保证 $\mathrm{lcp}[i-1]$ 是与所有更靠前后缀的最大公共前缀长度）；而长度超过它的前缀都是第一次出现。同时子数组不能含 $0$ ，所以可用的前缀长度不超过 $\mathrm{zf}[p]$ 。故该后缀贡献的新子数组数为

\max\bigl(0,\; \mathrm{zf}[\mathrm{sa}[i]] - \mathrm{lcp}[i-1]\bigr)

（排名最前的后缀取 $\mathrm{lcp}[-1] = 0$ ）。对 $i = 0,\dots,M-1$ 求和即得答案。

复杂度说明：官方题解用 SA-IS 算法（atcoder::suffix_array）在 $O(M)$ 内求出后缀数组，从而整体 $O(N)$ 。下面的参考代码为了自包含，实现了倍增法后缀数组，复杂度为 $O(M\log M) = O(N\log N)$ ，对本体数据量（ $N \le 5\times10^5$ ）也足够快。

参考代码

#include <bits/stdc++.h>
using namespace std;

// Doubling suffix array for integer string s (values >= 0), O(n log n), no sentinel
vector<int> suffix_array(const vector<int>& s) {
    int n = (int)s.size();
    vector<int> sa(n), rnk(n), tmp(n);
    // initial rank by compressed first character
    {
        vector<int> vals = s;
        sort(vals.begin(), vals.end());
        vals.erase(unique(vals.begin(), vals.end()), vals.end());
        for (int i = 0; i < n; i++)
            rnk[i] = lower_bound(vals.begin(), vals.end(), s[i]) - vals.begin();
        iota(sa.begin(), sa.end(), 0);
        stable_sort(sa.begin(), sa.end(), [&](int a, int b) { return rnk[a] < rnk[b]; });
    }
    for (int k = 1; k < n; k <<= 1) {
        int maxr = 0;
        for (int i = 0; i < n; i++) maxr = max(maxr, rnk[i]);
        // key2[i] = rnk[i+k]+1 if i+k < n else 0  (0 == "empty second half")
        vector<int> key2(n);
        for (int i = 0; i < n; i++) key2[i] = (i + k < n) ? rnk[i + k] + 1 : 0;
        // stable counting sort by key2
        vector<int> cnt(maxr + 2, 0);
        for (int i = 0; i < n; i++) cnt[key2[i]]++;
        for (int i = 1; i < maxr + 2; i++) cnt[i] += cnt[i - 1];
        vector<int> sa2(n);
        for (int i = n - 1; i >= 0; i--) sa2[--cnt[key2[i]]] = i;
        // stable counting sort by key1 = rnk
        fill(cnt.begin(), cnt.end(), 0);
        for (int i = 0; i < n; i++) cnt[rnk[i]]++;
        for (int i = 1; i <= maxr; i++) cnt[i] += cnt[i - 1];
        vector<int> sa3(n);
        for (int i = n - 1; i >= 0; i--) sa3[--cnt[rnk[sa2[i]]]] = sa2[i];
        sa.swap(sa3);
        // reassign ranks
        tmp[sa[0]] = 0;
        for (int i = 1; i < n; i++) {
            int a = sa[i - 1], b = sa[i];
            int ka = (a + k < n) ? rnk[a + k] : -1;
            int kb = (b + k < n) ? rnk[b + k] : -1;
            bool same = (rnk[a] == rnk[b] && ka == kb);
            tmp[sa[i]] = tmp[sa[i - 1]] + (same ? 0 : 1);
        }
        rnk.swap(tmp);
        if (rnk[sa[n - 1]] == n - 1) break;  // all ranks already distinct
    }
    return sa;
}

// Kasai LCP array: lcp[i] = LCP of sa[i-1] and sa[i]
vector<int> lcp_array(const vector<int>& s, const vector<int>& sa) {
    int n = (int)s.size();
    vector<int> rank(n);
    for (int i = 0; i < n; i++) rank[sa[i]] = i;
    vector<int> lcp(n - 1, 0);
    int h = 0;
    for (int i = 0; i < n; i++) {
        int r = rank[i];
        if (r == 0) { h = 0; continue; }
        int j = sa[r - 1];
        while (i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
        lcp[r - 1] = h;
        if (h) h--;
    }
    return lcp;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    // run-length encoding of A
    vector<pair<int, int>> lens;  // (value, run length)
    for (int i = 0; i < N; ) {
        int j = i;
        while (j < N && A[j] == A[i]) j++;
        lens.push_back({A[i], j - i});
        i = j;
    }

    // maximal usable blocks
    vector<pair<int, int>> maximals;
    {
        int idx = 0;
        int n = (int)lens.size();
        while (idx < n) {
            if (lens[idx].first > lens[idx].second) { idx++; continue; }
            int jlen = idx + 1;
            int jsee = jlen;
            while (jlen < n) {
                if (lens[jlen].first > lens[jlen].second) {
                    break;            // barrier: not included
                } else if (lens[jlen].first < lens[jlen].second) {
                    jsee = jlen + 1;  // included as the last run of the block
                    break;
                } else {
                    jlen++; jsee++;
                }
            }
            maximals.push_back({idx, jsee});
            idx = jlen;
        }
    }

    // build T : [0] ++ block values joined by 0
    vector<int> T = {0};
    for (auto [li, ri] : maximals) {
        for (int i = li; i < ri; i++) T.push_back(lens[i].first);
        T.push_back(0);
    }

    // count distinct subarrays of T that do not contain 0
    int m = (int)T.size();
    vector<int> sa = suffix_array(T);
    vector<int> lcp = lcp_array(T, sa);

    vector<int> zf(m + 1, 0);
    for (int i = m - 1; i >= 0; i--) {
        if (T[i] == 0) zf[i] = 0;
        else zf[i] = zf[i + 1] + 1;
    }

    long long ans = 0;
    for (int i = 0; i < m; i++) {
        long long l = (i == 0) ? 0 : lcp[i - 1];
        long long r = zf[sa[i]];
        ans += max(0LL, r - l);
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度：游程编码与块构造 $O(N)$ ；后缀数组若用 SA-IS 为 $O(M) = O(N)$ ，参考代码用倍增法为 $O(M\log M) = O(N\log N)$ ，其中 $M = |T| = O(N)$ 。
空间复杂度： $O(N)$

总结

本场题目的知识点分布：A、B 是热身题；C 强调"局部可行 ⟺ 整体可行"的转化与查表优化；D 的核心是 $g(X)$ 状态设计与单字符转移的单调性；E 展示了"按商分组 + 前缀和"处理 $\bmod$ 求和的经典手法；F 是滑动窗口 + 树状数组求区间逆序数；G 则需要游程编码、障碍符构造与后缀数组统计互异子串的综合能力。建议重点吃透 D、E、F 三题的方法，它们对应的技巧在后续竞赛中复用率很高。