AtCoder Beginner Contest 446 题解

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

AtCoder Beginner Contest 446 题解

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

比赛概览

本场整体难度适中，是一套结构标准的 ABC。A、B 是纯粹的入门与模拟题；C 需要意识到鸡蛋"先购先食"即 FIFO，用队列维护即可，晚上丢弃一步是易错点；D 把"最长连续上升子序列"转化为按值 DP 的经典题；E 将线性递推看成图上的自动机，用反向 BFS 一次判定所有起点；F 和 G 是本场难度最高、区分度最大的两题——F 需要增量式地维护"可达集"与"出边邻居集"，G 需要建立"221 子序列 ↔ 块尾下标序列"的双射并配合前缀和 DP。E、F、G 涉及的反向图 BFS、增量可达性、去重计数 DP 是值得重点掌握的竞赛技巧。

A - Handmaid

题目链接：https://atcoder.jp/contests/abc446/tasks/abc446_a

题目大意

给定一个人名 $S$ （首字母为大写英文字母，其余为小写英文字母），它的侍女的名字为：先把 $S$ 的首字母转为小写，再在开头拼接 Of。输出侍女的名字。

思路

按照题意直接模拟两步即可：

将 $S$ 的首字母转为小写；
在开头拼上 Of。

由于题目保证 $S$ 除首字母外其余字符都是小写，因此"把整个字符串转小写"与"只转首字母"是等价的。注意几个实现细节：

C++ 的 tolower 接收 unsigned char 并返回 int，赋值给 char 时需强转；本题字符串中只有 ASCII 字符，直接用即可。
Python 中 s.lower() 一步到位。

正确性显然：这就是题面定义的变换，没有歧义。

参考代码

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

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

    string s;
    cin >> s;
    s[0] = (char)tolower((unsigned char)s[0]);   // 首字母转小写
    cout << "Of" << s << '\n';                    // 开头拼接 "Of"
    return 0;
}

s = input()
print("Of" + s.lower())

复杂度分析

时间复杂度： $O(|S|)$ ，其中 $|S| \le 10$ 。
空间复杂度： $O(|S|)$ 。

B - Greedy Draft

题目链接：https://atcoder.jp/contests/abc446/tasks/abc446_b

题目大意

有 $N$ 个顾客和 $M$ 种罐装果汁。顾客 $i$ 有一份长度为 $L_i$ 的愿望清单 $X_{i,1},\dots,X_{i,L_i}$ （元素互异）。顾客 $1,\dots,N$ 按顺序选择饮料：若其愿望清单中有尚未被任何人选走的果汁，则选择清单中编号最早出现的那个；否则得到水。输出每个顾客获得的果汁编号，得到水则输出 0。

思路

直接模拟。用一个布尔数组 used[1..M] 记录每种果汁是否已被选走，然后按顾客顺序处理：

从顾客 $i$ 的清单第一个元素开始扫描，遇到第一个 used 为假的果汁就选定它、标记为已用并停止扫描；
若整个清单扫完都没有未使用的果汁，则顾客 $i$ 得到水，输出 $0$ 。

正确性：每个顾客的决策只依赖"当前已被选走的果汁集合"，与题面描述的流程完全一致；由于清单元素互异，不会出现重复判断的问题。

边界情况：如果某顾客的清单恰好覆盖了全部 $M$ 种且都已被选走，则输出 $0$ ；这也是水存在的原因（ $M$ 种果汁选完后，后来者只能喝水）。

参考代码

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

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

    int N, M;
    cin >> N >> M;

    vector<int> used(M + 1, 0);      // used[j] = 1 表示果汁 j 已被选走
    for (int i = 0; i < N; i++) {
        int L;
        cin >> L;
        vector<int> X(L);
        for (int j = 0; j < L; j++) cin >> X[j];

        int ans = 0;                 // 0 表示得到水
        for (int j = 0; j < L; j++) {
            if (!used[X[j]]) {
                used[X[j]] = 1;
                ans = X[j];
                break;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

n, m = map(int, input().split())
used = set()
for _ in range(n):
    l = int(input())
    lst = list(map(int, input().split()))
    ans = 0
    for v in lst:
        if v not in used:
            used.add(v)
            ans = v
            break
    print(ans)

复杂度分析

时间复杂度： $O(\sum_i L_i) \le O(NM)$ ，其中 $N, M \le 100$ 。
空间复杂度： $O(M)$ 。

C - Omelette Restaurant

题目链接：https://atcoder.jp/contests/abc446/tasks/abc446_c

题目大意

餐厅营业 $N$ 天。第 $i$ 天早晨购入 $A_i$ 个鸡蛋；中午使用 $B_i$ 个鸡蛋（先购入的先用）；晚上丢弃所有已存放 $D$ 天及以上的鸡蛋。已知早晨第 $1$ 天前没有库存，且每天中午都不会缺蛋。求第 $N$ 天晚上操作之后剩余的鸡蛋数。共有 $T$ 组数据，保证所有数据的 $\sum N \le 2\times 10^5$ 。

思路

关键观察："先购入的先用"意味着鸡蛋的消耗顺序是严格的 FIFO（先进先出），因此可以用一个队列来维护库存中每个鸡蛋的购入日期。

设队列中元素为购入日（第 $i$ 天购入的元素记为 $i$ ），每天依次执行三个操作：

早晨：把 $A_i$ 个元素 $i$ 从队尾入队。
中午：从队头弹出 $B_i$ 个元素（使用最早购入的鸡蛋）。题目保证不会弹空。
晚上：丢弃已存放 $D$ 天及以上的鸡蛋。在第 $i$ 天，这些鸡蛋的购入日满足 $j \le i-D$ 。由于队列中的购入日总是非递减的，若还存在购入日 $\le i-D$ 的鸡蛋，它们必然连续地位于队头；而购入日 $< i-D$ 的鸡蛋在前一天（第 $i-1$ 天）晚上就已经被丢弃了，所以只需反复检查队头是否为 $i-D$ 并弹出即可，无需扫描整条队列。

最终答案就是第 $N$ 天晚上操作后队列的大小。

正确性：队列非递减的性质保证了"弹出队头"与"使用最早购入的鸡蛋"一致；晚上丢弃时，购入日比 $i-D$ 更早的鸡蛋已经被处理掉，所以队头只会是 $i-D$ 或更大的日期，检查队头即可完成全部丢弃。

复杂度：每天入队 $A_i$ 次、出队 $B_i$ 次，总操作数为 $O\bigl(\sum_i (A_i+B_i)\bigr) = O(N \cdot \max A_i)$ ；由于 $\max A_i \le 10$ 且所有数据的 $\sum N \le 2\times 10^5$ ，总操作量不超过约 $2\times 10^6$ ，非常宽裕。

参考代码

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

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

    int T;
    cin >> T;
    while (T--) {
        int N, D;
        cin >> N >> D;
        vector<int> A(N), B(N);
        for (int i = 0; i < N; i++) cin >> A[i];
        for (int i = 0; i < N; i++) cin >> B[i];

        queue<int> q;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < A[i]; j++) q.push(i);          // 早晨：购入 A[i] 个
            for (int j = 0; j < B[i]; j++) q.pop();            // 中午：使用 B[i] 个
            while (!q.empty() && q.front() == i - D) q.pop();  // 晚上：丢弃存放 >= D 天的
        }
        cout << (int)q.size() << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度：每个用例 $O(N \cdot \max A_i)$ ；所有用例合计 $O(\sum N \cdot \max A_i) = O(2\times 10^6)$ 。
空间复杂度： $O(\sum_i A_i) \le O(10N)$ （队列中最多同时存在的鸡蛋数）。

D - Max Straight

题目链接：https://atcoder.jp/contests/abc446/tasks/abc446_d

题目大意

给定长度为 $N$ 的整数序列 $A$ ，求满足 $B_{i+1}=B_i+1$ 的子序列 $B$ 的最大长度。也就是说， $B$ 必须是形如 $v,\ v+1,\ v+2,\ \dots,\ v+k-1$ 的连续递增整数。

思路

问题转化：要求找的是"连续上升"的子序列——相邻两项差恰好为 $1$ 。注意到子序列中元素的取值决定了一切：若选择了值 $v$ ，那么下一个必须选更大的 $v+1$ 。因此可以按值做 DP。

设 $dp[v]$ 表示"以值 $v$ 结尾的合法子序列的最大长度"。从左到右扫描 $A$ ，遇到元素 $a$ 时更新：

dp[a] = \max\bigl(dp[a],\ dp[a-1]+1\bigr)

$dp[a-1]+1$ 表示把当前这个 $a$ 接到某个"以 $a-1$ 结尾的最长子序列"之后；
由于 $dp[a-1]$ 只由当前元素之前的元素构成，两个子序列不会重复使用元素，故该转移合法；
保留 $dp[a]$ 原值，是因为 $a$ 可能已经在更早的位置出现过，且那次出现能拼出更长的序列。

最终答案是 $\max_v dp[v]$ 。注意长度为 $1$ 的子序列总是合法的，所以答案至少为 $1$ 。

为什么用哈希表/映射存储： $A_i$ 可达 $10^9$ ，无法直接开数组，但"值"的数量至多 $N$ 个，用 unordered_map（或 map）按需记录即可。 $a=1$ 时 $dp[0]$ 不存在，默认取 $0$ ，于是 $dp[1]=\max(dp[1],1)$ ，正确。

参考代码

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

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

    int n;
    cin >> n;
    unordered_map<int, int> dp;      // dp[v] = 以值 v 结尾的最长连续上升子序列长度
    int ans = 0;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        dp[a] = max(dp[a], dp[a - 1] + 1);   // 把 a 接到以 a-1 结尾的子序列之后
        ans = max(ans, dp[a]);
    }
    cout << ans << '\n';
    return 0;
}

from collections import defaultdict

n = int(input())
a = list(map(int, input().split()))
d = defaultdict(int)
for v in a:
    d[v] = max(d[v], d[v - 1] + 1)
print(max(d.values()))

复杂度分析

时间复杂度： $O(N)$ 期望（使用 unordered_map；若用 map 则为 $O(N\log N)$ ）。
空间复杂度： $O(N)$ （不同值的个数）。

E - Multiple-Free Sequences

题目链接：https://atcoder.jp/contests/abc446/tasks/abc446_e

题目大意

求满足以下条件的整数对 $(x,y)$ 的数量（ $0\le x,y\le M-1$ ）：由 $s_1=x,\ s_2=y,\ s_n=As_{n-1}+Bs_{n-2}\ (n\ge 3)$ 定义的无穷序列中不含有 $M$ 的倍数。其中 $2\le M\le 1000$ 。

思路

Step 1：模 $M$ 化简。 倍数条件只关心 $s_n \bmod M$ ，故把递推式改为

s_n \equiv (A s_{n-1} + B s_{n-2}) \pmod M,

此时所有项都在 $[0,M-1]$ 内，"序列含 $M$ 的倍数"就等价于"序列中出现 $0$ "。

Step 2：看成自动机/图。 把相邻两项组成的二元组 $(s_{n-1},s_n)$ 看作状态，共 $M^2$ 个状态。从状态 $(x,y)$ 出发的转移是唯一的：

(x,y)\ \longrightarrow\ \bigl(y,\ (Ay+Bx)\bmod M\bigr).

从初态 $(x,y)$ 走若干步到达的状态恰为 $(s_k,s_{k+1})$ 。因此"序列中出现 $0$ "等价于：从初态 $(x,y)$ 出发，能到达某个第一坐标或第二坐标为 $0$ 的状态。记目标集合

W=\{(0,t)\mid 0\le t<M\}\cup\{(t,0)\mid 0\le t<M\}.

Step 3：反向 BFS 一次性判定所有起点。 若对每个起点分别做 DFS，复杂度会达到 $O(M^4)$ 。注意到"从 $v$ 出发能到达某个 $w\in W$ "当且仅当"在反向图中，从某个 $w\in W$ 能到达 $v$ "。于是：

对每个状态 $(x,y)$ ，求出其正向后继 $(y,(Ay+Bx)\bmod M)$ ，并加一条反向边：后继 → $(x,y)$ ；
在反向图上从 $W$ 中所有状态出发做一次 BFS，被访问到的状态就是"序列中会出现 $0$ "的起点；
未被访问的状态数即为答案。

正确性：正向图与反向图之间的可达关系是互补的，一次多源 BFS 正好把所有"会命中 $0$ "的状态都标记出来，其余状态对应的序列永远不会出现 $0$ 。注意 $W$ 要包含第一坐标或第二坐标为 $0$ 的全部状态（包括 $(0,0)$ ），因为 $s_1$ 或 $s_2$ 本身为 $0$ 就已含倍数。

复杂度：状态数 $M^2$ 、反向边数 $M^2$ ，BFS 总复杂度 $O(M^2)$ ，对 $M\le 1000$ 绰绰有余。

参考代码

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

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

    int M, A, B;
    cin >> M >> A >> B;

    int S = M * M;
    vector<vector<int>> g(S);          // 反向图：g[后继] 里存所有前驱
    for (int x = 0; x < M; x++) {
        for (int y = 0; y < M; y++) {
            int nx = y;                              // 后继的第一坐标
            int ny = (A * y + B * x) % M;            // 后继的第二坐标
            g[nx * M + ny].push_back(x * M + y);     // 反向边：后继 -> (x,y)
        }
    }

    vector<int> seen(S, 0);
    queue<int> que;
    for (int x = 0; x < M; x++) {
        for (int y = 0; y < M; y++) {
            if ((x == 0 || y == 0) && !seen[x * M + y]) {   // 目标集合 W
                seen[x * M + y] = 1;
                que.push(x * M + y);
            }
        }
    }

    while (!que.empty()) {
        int v = que.front();
        que.pop();
        for (int u : g[v]) {
            if (!seen[u]) {
                seen[u] = 1;
                que.push(u);
            }
        }
    }

    int ans = 0;
    for (int x = 0; x < M; x++)
        for (int y = 0; y < M; y++)
            if (!seen[x * M + y]) ans++;   // 反向不可达 = 序列永远不出现 0
    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(M^2)$ 。
空间复杂度： $O(M^2)$ 。

F - Reachable Set 2

题目链接：https://atcoder.jp/contests/abc446/tasks/abc446_f

题目大意

给定 $N$ 个顶点、 $M$ 条边的有向图 $G$ 。对每个 $k=1,2,\dots,N$ ，问：能否删除若干顶点（连同其关联边，可以删 $0$ 个），使得从顶点 $1$ 出发恰好能到达且只能到达顶点 $1,2,\dots,k$ ？若可行，输出所需删除的最小顶点数；否则输出 $-1$ 。图可能不连通、有重边或自环。

思路

Step 1：转化为子图可达性。 记 $G_i$ 为删除顶点 $i+1,\dots,N$ 后得到的子图（等价于只保留编号 $\le i$ 的顶点及其间的全部边，含自环）。

关键引理： $k=i$ 时目标可达，当且仅当在 $G_i$ 中顶点 $1,2,\dots,i$ 全部从顶点 $1$ 可达。

充分性：若 $1..i$ 在 $G_i$ 中全部可达，那么把"与某个可达顶点有出边相连、且编号 $>i$ "的顶点全部删除。这样任何从 $1$ 出发、试图到达 $>i$ 顶点的路径上，第一个编号 $>i$ 的顶点必然是该路径起点（可达顶点）的出边邻居，因而被删除，路径被截断。于是从 $1$ 可达的顶点恰好是 $1..i$ 。
必要性：若某个 $j\le i$ 在 $G_i$ 中不可达，那么任何从 $1$ 到 $j$ 的路径都必须经过编号 $>i$ 的顶点（因为 $G_i$ 已包含全部只用 $\le i$ 顶点的路径），这会导致可达集包含编号 $>i$ 的顶点，与目标矛盾。

Step 2：最小删除数。 若 $k=i$ 可行，顶点 $1..i$ 不可删除，因此任何"与可达顶点 $u\in\{1..i\}$ 之间有出边 $u\to v$ 、且 $v>i$ "的顶点 $v$ 都会立刻变得可达，必须删除；反过来删掉所有这样的 $v$ 即可达成目标（理由同充分性证明）。所以

\text{最小删除数}=\Bigl|\Bigl\{v:\ v\ \text{是某个可达顶点的出边邻居}\Bigr\}\setminus\{1,\dots,i\}\Bigr|.

Step 3：增量维护两个集合。 按 $i=1,2,\dots,N$ 依次加入顶点 $i$ 及其连向编号 $\le i$ 顶点的边。维护：

vis（可达集）： $G_i$ 中从 $1$ 可达的顶点；
can（出边邻居集）：与某个可达顶点有出边相连的顶点（包含可达顶点自身）。

第 $i$ 轮时，若 $i\in\texttt{can}$ （即存在可达顶点连向 $i$ ），则顶点 $i$ 成为新可达顶点，从 $i$ 出发做一次 DFS，只沿"编号 $\le i$ "的边扩展，找出所有新可达顶点；DFS 过程中对每个遍历到的顶点，把它的全部出边邻居（不管编号是否 $\le i$ ）标记进 can，以便这些顶点在轮到它们时被处理。

第 $i$ 轮结束后：

若 $|\texttt{vis}|=i$ （ $1..i$ 全部可达），输出 $|\texttt{can}|-|\texttt{vis}|$ ；
否则输出 $-1$ 。

为什么每个顶点只被 DFS 一次：DFS 只访问编号 $\le i$ 且此前未访问的顶点，而一个顶点 $v$ 只有在编号 $\ge v$ 的轮次才可能被访问，所以它第一次成为可达顶点时就被处理，之后不会再被访问。相应地每条边至多被扫描一次，总复杂度 $O(N+M)$ 。

易错点：不能从编号 $>i$ 的顶点继续扩展（那会泄露到尚未加入的顶点）；但 can 标记不受此限制——它的作用只是"预告"未来轮次中哪个顶点会被加入并立刻可达。

参考代码

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

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

    int N, M;
    cin >> N >> M;
    vector<vector<int>> e(N);
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        --u;
        --v;
        e[u].push_back(v);
    }

    vector<int> vis(N, 0), can(N, 0);
    int cvis = 0, ccan = 0;

    for (int i = 0; i < N; i++) {
        if (i == 0) {           // 顶点 1 恒可达
            can[0] = 1;
            ccan++;
        }
        if (can[i]) {
            // 迭代式 DFS：只沿编号 <= i 的边扩展
            vector<int> st;
            st.push_back(i);
            while (!st.empty()) {
                int v = st.back();
                st.pop_back();
                if (vis[v]) continue;
                vis[v] = 1;
                cvis++;
                for (int u : e[v]) {
                    if (!vis[u] && u <= i) st.push_back(u);
                    if (!can[u]) {          // 出边邻居一律标记，无论编号大小
                        can[u] = 1;
                        ccan++;
                    }
                }
            }
        }
        if (cvis == i + 1) cout << (ccan - cvis) << '\n';   // 可行：删除出边邻居中不可达的部分
        else cout << -1 << '\n';
    }
    return 0;
}

复杂度分析

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

G - 221 Subsequence

题目链接：https://atcoder.jp/contests/abc446/tasks/abc446_g

题目大意

称一个正整数组 $X$ 为 221 序列，如果其游程编码中每一个（长度, 值）对都满足"长度 = 值"。例如 $(2,2,3,3,3,1,2,2)$ 是 221 序列（块分别为 $2^2,3^3,1^1,2^2$ ），而 $(1,1)$ 、 $(4,4,1,4,4)$ 不是。

给定序列 $A$ （ $1\le N\le 5\times 10^5$ ， $1\le A_i\le N$ ），求 $A$ 的非空子序列中有多少个是 221 序列，答案对 $998244353$ 取模。相同值序列的子序列只算一次（即使取自不同位置）。

思路

Step 1：规范化下标（贪心）。 对一个值序列 $B=(B_1,\dots,B_k)$ ，定义它在 $A$ 中的贪心下标序列 $T=(t_1,\dots,t_k)$ ：

t_1=\min\{u: A_u=B_1\},\qquad t_i=\min\{u>t_{i-1}: A_u=B_i\}\ (i\ge 2).

即在 $A$ 中每次取"上一次取完之后、能匹配 $B_i$ 的最靠前位置"。这是实现 $B$ 的字典序最小的下标序列，且是唯一的（可由贪心证明：任一合法下标序列的第 $i$ 个位置都不小于 $t_i$ ，归纳即可）。因此"不同位置取出的相同值序列"对应到同一条贪心下标序列，去重有了抓手。

Step 2：块尾下标序列 $P$ 。 对一条属于 221 序列的子序列 $B$ ，取其贪心下标序列 $T$ 。由于 $B$ 的每个"块"内值全部相同，令

P=(p_1,\dots,p_m)

为 $T$ 中每个块最后一个元素在 $A$ 中的下标（ $p_i=t_{v_1+\cdots+v_i}$ ，其中 $v_i$ 是第 $i$ 个块的值）。反向地，给定 $P$ 也能唯一重建 $B$ ：第 $i$ 个块就是 $A_{p_i}$ 个值为 $A_{p_i}$ 的元素，贪心地从位置 $p_{i-1}$ 之后开始取。于是：

不同的 221 子序列（按值去重）与合法的 $P$ 一一对应。

问题转化为：统计满足下列条件的下标序列 $P=(p_1,\dots,p_m)$ 的个数（ $m\ge 1$ ）：

$A_{p_{i-1}}\ne A_{p_i}$ （定义哨兵 $p_0:=0,\ A_0:=0$ ，相邻块值必须不同，否则两个块会合并、长度不再等于值）；
区间 $(p_{i-1},p_i]$ 内恰好有 $A_{p_i}$ 个元素等于 $A_{p_i}$ （第 $i$ 个块要凑够"长度 = 值"个同值元素，且贪心取法正好取走区间内全部同值元素，最后一个恰在 $p_i$ ）。

Step 3：用"第几次出现"重写条件。 设 $C_t$ 为 $A_1,\dots,A_t$ 中等于 $A_t$ 的个数（即 $A_t$ 在位置 $t$ 处是第 $C_t$ 次出现），并定义 $J(x,c)$ 为值 $x$ 第 $c$ 次出现的位置（ $c\ge 1$ ），约定 $J(x,0)=-1$ 。

取 $p=p_i$ 、 $x=A_p$ ，则 $C_p=c$ 且 $p$ 是 $x$ 的第 $c$ 次出现。条件"区间 $(q,p]$ 中恰好有 $x$ 个 $x$ "等价于： $q$ 严格落在第 $(c-x)$ 次与第 $(c-x+1)$ 次出现之间，即

J(x,\,c-x) < q < J(x,\,c-x+1).

这个条件同时自动保证了 $A_q\ne x$ （因为 $q$ 位于 $x$ 的两次连续出现之间）。显然还需要 $c\ge x$ ，否则 $x$ 的出现次数连一个块都凑不齐。

Step 4：DP 与前缀和。 定义 $dp[p]$ 为以位置 $p$ 结尾的合法 $P$ 的数量，并约定 $dp[0]=1$ 表示"空序列"（即当前块是第一个块）。则

dp[p]=\sum_{q=J(x,c-x)+1}^{J(x,c-x+1)-1} dp[q].

分三种情况处理：

若 $c<x$ ： $dp[p]=0$ ；
若 $c=x$ ： $J(x,0)=-1$ ，求和从 $0$ 开始， $q=0$ 对应空序列，贡献 $dp[0]=1$ ，故 $dp[p]=1+\sum_{q=1}^{J(x,1)-1}dp[q]$ ；
若 $c>x$ ：直接按上式求和。

由于 $dp$ 是按位置递增顺序计算的，且查询都是前缀和区间查询，用前缀和数组即可 $O(1)$ 完成每个区间的求和（点更新一次、位置递增，无需线段树）。

最终答案

\text{ans}=\sum_{p=1}^{N} dp[p]\pmod{998244353}.

注意空序列（ $dp[0]$ ）不计入答案。

正确性小结：Step 2 建立了 221 子序列与合法 $P$ 的双射，Step 3 把块条件精确翻译成关于"第几次出现"的不等式，Step 4 的 DP 按定义枚举合法的前一位置 $q$ 并求和；每一步都等价于原始条件，因此计数正确。使用前缀和的要点是 $dp$ 按序确定，区间查询与单点更新都可 $O(1)$ 完成。

参考代码

#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);
    for (int i = 0; i < N; i++) cin >> a[i];

    vector<int> precnt(N);            // precnt[i] = i 之前与 a[i] 相同的元素个数
    vector<vector<int>> idxs(N + 1);  // idxs[v] = 值 v 出现的位置（递增）
    for (int i = 0; i < N; i++) {
        precnt[i] = (int)idxs[a[i]].size();
        idxs[a[i]].push_back(i);
    }

    const long long MOD = 998244353;
    vector<long long> dp(N, 0), acc(N + 1, 0);   // acc[j] = dp[0]+...+dp[j-1]

    for (int i = 0; i < N; i++) {
        int x = a[i], c = precnt[i];   // 第 c 次出现之前已有 c 个 x，i 是第 c+1 次出现
        long long val = 0;
        if (c < x - 1) {
            val = 0;                                        // 出现次数不足一个块
        } else if (c == x - 1) {
            // c+1 == x：前驱可以是空序列(+1) 或 位于第一个 x 之前的位置
            val = (acc[idxs[x][0]] + 1) % MOD;
        } else {
            // 前驱严格位于第 (c-x) 次与第 (c-x+1) 次出现之间
            int L = idxs[x][c - x];
            int R = idxs[x][c - x + 1];
            val = (acc[R] - acc[L + 1] + MOD) % MOD;
        }
        dp[i] = val;
        acc[i + 1] = (acc[i] + dp[i]) % MOD;
    }

    long long ans = 0;
    for (int i = 0; i < N; i++) ans = (ans + dp[i]) % MOD;
    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(N)$ （预处理 $O(N)$ ，DP 中每步区间求和 $O(1)$ ）。
空间复杂度： $O(N)$ 。