AtCoder Beginner Contest 435 题解

项目	内容
比赛时间	2025-12-06
比赛链接	https://atcoder.jp/contests/abc435
题目数量	A–G 共 7 题

比赛概览

本场整体难度平稳，A、B 为签到题；C 是经典的单向连锁反应扫描，注意 $N$ 高达 $5\times 10^5$；D 考察"反图 + 在线传播"的均摊思想；E 是区间覆盖的经典题，用有序集合维护白色连续段即可。F 是本场第一个有明显区分度的题，需要把"拆塔运动"归约到笛卡尔树上的树形 DP；G 是压轴计数题，核心是把递推 $dp[i][c]=S_{i-2}-dp[i-2][c]$ 用"懒标记 + 进入/离开事件"批量加速到 $O(N+M)$。建议重点掌握 E、F、G 的处理手法。

---

A - Triangular Number

题目链接：https://atcoder.jp/contests/abc435/tasks/abc435_a

题目大意

给定正整数 $N$（$1\le N\le 100$），输出 $1+2+\cdots+N$。

思路

这是最直接的求和问题，两种做法均可：

1. 用循环累加 $1$ 到 $N$；
2. 用等差数列求和公式

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

由于 $N\le 100$，两种做法都轻而易举；用公式时注意 $N(N+1)$ 最大为 $10100$，用 int 即可，但写成 long long 更稳妥。

参考代码

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

int main() {
    int n;
    cin >> n;
    cout << 1LL * n * (n + 1) / 2 << '\n';
    return 0;
}

官方题解给出了循环写法，也一并附上（Python）：

n = int(input())
ans = 0
for i in range(1, n + 1):
    ans += i
print(ans)

复杂度分析

• 时间复杂度：$O(N)$（循环）或 $O(1)$（公式）
• 空间复杂度：$O(1)$

---

B - No-Divisible Range

题目链接：https://atcoder.jp/contests/abc435/tasks/abc435_b

题目大意

给定长度为 $N$（$1\le N\le 50$）的正整数序列 $A$，统计满足下列条件的整数对 $(l,r)$（$1\le l\le r\le N$）的个数：

对区间内每一个 $i$（$l\le i\le r$），$A_i$ 不是 $A_l+A_{l+1}+\cdots+A_r$ 的约数。

思路

关键观察：对于正整数 $X,Y$，"$X$ 是 $Y$ 的约数"等价于"$Y$ 除以 $X$ 的余数为 $0$"。因此对一个固定的 $(l,r)$：

1. 先求出区间和 $S=A_l+\cdots+A_r$；
2. 再逐个检查 $i\in[l,r]$：若存在某个 $i$ 使得 $S\bmod A_i=0$，则 $(l,r)$ 不合法；否则合法。

$N\le 50$，候选区间总数只有 $\frac{N(N+1)}{2}\le 1275$ 个，对每个区间求和与检查都是 $O(N)$，总复杂度 $O(N^3)$，绰绰有余。

易错点：当 $A_i=1$ 时，$1$ 是任何正整数的约数，所以任何包含 $1$ 的区间必然不合法（如样例 2）。这是自然被余数判据覆盖的，无需特判，但要意识到这一点以防手算时出错。

参考代码

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    int ans = 0;
    for (int l = 0; l < n; l++) {
        for (int r = l; r < n; r++) {
            int s = 0;
            for (int i = l; i <= r; i++) s += a[i];
            bool ok = true;
            for (int i = l; i <= r; i++) {
                if (s % a[i] == 0) { ok = false; break; }
            }
            if (ok) ans++;
        }
    }
    cout << ans << '\n';
    return 0;
}

官方题解 Python 版：

n = int(input())
a = list(map(int, input().split()))
ans = 0

for i in range(n):
    for j in range(i + 1):
        s = 0
        for k in range(j, i + 1):
            s += a[k]
        flag = True
        for k in range(j, i + 1):
            if s % a[k] == 0:
                flag = False
        if flag:
            ans += 1

print(ans)

复杂度分析

• 时间复杂度：$O(N^3)$
• 空间复杂度：$O(N)$（存序列）

---

C - Domino

题目链接：https://atcoder.jp/contests/abc435/tasks/abc435_c

题目大意

数轴上有 $N$ 个多米诺骨牌，第 $i$ 个骨牌位于坐标 $i$、高度 $A_i$。当第 $i$ 个骨牌向右倒下时，区间 $[i,\ i+A_i-1]$ 内的所有骨牌都会向右倒。若第 $1$ 个骨牌向右倒，最终一共有多少个骨牌倒下？

（$1\le N\le 5\times 10^5$，$1\le A_i\le N$）

思路

关键观察：连锁反应只会从左向右单调推进。因为每个骨牌只能使右侧的骨牌倒下，所以一旦某个骨牌 $i$ 没有倒下，那么它右侧的所有骨牌都不可能倒下——连锁已经终止。

算法：维护变量 $R$ 表示"目前最右倒下的坐标"。初始时第 $1$ 个骨牌自己倒下，故 $R=1$。从左到右扫描 $i=1,2,\ldots$：

• 若 $i>R$，说明第 $i$ 个骨牌未倒下，连锁到此结束，答案为 $R$；
• 否则第 $i$ 个骨牌已经倒下，它倒下会波及到坐标 $i+A_i-1$，更新 $R=\max(R,\ \min(N,\ i+A_i-1))$。

为什么正确：任意时刻所有已倒下的骨牌都落在 $[1,R]$ 内（归纳：第 $i$ 个骨牌倒下时它在 $[1,R]$ 内，且它的波及范围全部纳入 $R$）。由于倒下传播是单调的，$R$ 达到某个值后不再增长，扫描到 $i>R$ 时即可确认不会再有任何骨牌倒下。

边界情况：$i+A_i-1$ 可能超过 $N$（因为 $A_i\le N$ 但 $i$ 也可以较大），需要与 $N$ 取 $\min$，防止越界。

参考代码

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    int R = 1; // 最右倒下的坐标，初始为第 1 个
    for (int i = 1; i <= n; i++) {
        if (i > R) break;           // 第 i 个未倒下，连锁终止
        R = max(R, min(n, i + a[i] - 1));
    }
    cout << R << '\n';
    return 0;
}

官方题解 Python 版（注意其中坐标从 $0$ 开始）：

N = int(input())
A = list(map(int, input().split()))

crr = 1  # 坐标小于 crr 的骨牌都已倒下
for i in range(N):
    if i >= crr:          # 骨牌 i 未倒下，连锁结束
        print(i)
        exit()
    crr = max(crr, i + A[i])

print(N)

复杂度分析

• 时间复杂度：$O(N)$
• 空间复杂度：$O(N)$

---

D - Reachability Query 2

题目链接：https://atcoder.jp/contests/abc435/tasks/abc435_d

题目大意

给定一个 $N$ 个点、$M$ 条边的有向图，第 $i$ 条边为 $X_i\to Y_i$。初始所有点为白色。按顺序处理 $Q$ 个查询：

• 1 v：把点 $v$ 染黑；
• 2 v：询问从点 $v$ 出发，沿有向边能否到达某个黑点。

（$N,M,Q\le 3\times 10^5$）

思路

关键转化：把图中所有边反向，得到反图 $G'$。原图中"从 $v$ 能到达黑点 $b$"等价于反图中"从黑点 $b$ 能到达 $v$"。因此查询 2 v 就变成：在反图中，$v$ 是否"从某个黑点可达"。

维护标记：设 $A_v$ 表示"反图中 $v$ 是否从某个黑点可达"。查询 2 v 直接输出 $A_v$，$O(1)$ 完成。

查询 1 v（把 $v$ 染黑）：在反图中从 $v$ 出发做 BFS/DFS，把经过的所有点标记为"可达"（$A_u\leftarrow 1$）。关键是只在 $A_u$ 从 false 变成 true 时才继续扩展它的出边。

为什么均摊 $O(N+M)$：若 $A_v$ 已经为 true，说明从之前的黑点已经能到达 $v$，那么 $v$ 能到达（反图中）的所有点必然也已经被标记过，此时染色 $v$ 不会带来任何新信息，直接跳过 BFS。每个点至多被"首次标为 true"一次，而 BFS 只会在首次标 true 时扫描它的出边，因此每条边在整个过程中至多被遍历一次。总的复杂度为 $O(Q+N+M)$。

易错点：注意 BFS 是在反图上进行的，即从 $v$ 出发访问的是所有"在原图中指向 $v$ 的点"。

参考代码

#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>> radj(n + 1); // 反图
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        radj[y].push_back(x); // 原图 x->y，反图中 y->x
    }

    int q;
    cin >> q;
    vector<char> reach(n + 1, 0); // 反图中是否从黑点可达
    queue<int> que;

    while (q--) {
        int t, v;
        cin >> t >> v;
        if (t == 1) {
            if (reach[v]) continue; // 已可达，染色无新信息
            reach[v] = 1;
            que.push(v);
            while (!que.empty()) {
                int u = que.front();
                que.pop();
                for (int w : radj[u]) {
                    if (!reach[w]) {
                        reach[w] = 1;
                        que.push(w);
                    }
                }
            }
        } else {
            cout << (reach[v] ? "Yes" : "No") << '\n';
        }
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(Q+N+M)$（每个点、每条边至多被处理一次）
• 空间复杂度：$O(N+M)$

---

E - Cover query

题目链接：https://atcoder.jp/contests/abc435/tasks/abc435_e

题目大意

有 $N$ 个格子排成一行（$1\le N\le 10^9$），初始全部为白色。依次处理 $Q$ 个查询（$Q\le 2\times 10^5$），第 $i$ 个查询给出 $(L_i,R_i)$，把 $[L_i,R_i]$ 内所有格子染黑（白变黑，黑保持不变），并输出当前白色格子的总数。

思路

$N$ 高达 $10^9$，逐格处理不可行，但 $Q\le 2\times 10^5$，因此只需要维护白色格子的连续段（区间）。

状态表示：用一个有序集合维护当前所有白色连续段 $\{[l_1,r_1],[l_2,r_2],\ldots\}$，初始为 $[1,N]$；另外用变量 $\text{white}$ 维护白色格子的总数。

处理查询 $(L,R)$：

1. 找到第一个满足 $r_i\ge L$ 的白色段（用有序集合的 lower_bound 定位）；
2. 依次处理所有与 $[L,R]$ 相交的白色段（即 $l_i\le R$ 的段）：
   • 整段被覆盖（$L\le l_i$ 且 $r_i\le R$）：直接删除该段；
   • 左侧露出（$l_i<L$）：删除原段，插入残段 $[l_i,L-1]$；
   • 右侧露出（$R<r_i$）：删除原段，插入残段 $[R+1,r_i]$；
   • 两侧都露出：删除原段，插入两个残段；
   • 每删除一个段，就从 $\text{white}$ 中减去它与 $[L,R]$ 的交集长度 $\min(r_i,R)-\max(l_i,L)+1$；
3. 输出 $\text{white}$。

为什么均摊高效：每个查询至多新增 $2$ 个残段（左侧露出 + 右侧露出），而被整段删除的白色段数量在全部查询中总和为 $O(Q)$（因为每新增一个段最多被删除一次）。因此总操作次数为 $O(Q)$，每次 lower_bound/插入/删除都是 $O(\log Q)$，总复杂度 $O(Q\log Q)$。

实现细节：集合中存二元组 $(r_i,l_i)$（右端点在前面），这样 lower_bound({L, -1}) 就能直接找到第一个 $r_i\ge L$ 的段；从该段起向后扫描，直到 $R<l_i$ 停止。

参考代码

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

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

    int n, q;
    cin >> n >> q;
    set<pair<int, int>> st; // 存 (r, l) 表示白色段 [l, r]
    st.insert({n, 1});
    long long white = n;

    while (q--) {
        int L, R;
        cin >> L >> R;
        auto it = st.lower_bound({L, -1}); // 第一个 r >= L 的段
        vector<pair<int, int>> add;
        while (it != st.end()) {
            int l = it->second, r = it->first;
            if (R < l) break; // 之后的段都与 [L,R] 不相交
            // 交叠部分被染黑
            white -= min(r, R) - max(l, L) + 1;
            if (l < L) add.push_back({L - 1, l}); // 左侧残段 [l, L-1]
            if (R < r) add.push_back({r, R + 1}); // 右侧残段 [R+1, r]
            it = st.erase(it);
        }
        for (auto &p : add) st.insert(p);
        cout << white << '\n';
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(Q\log Q)$（均摊）
• 空间复杂度：$O(Q)$（白色段数量有界）

---

F - Cat exercise

题目链接：https://atcoder.jp/contests/abc435/tasks/abc435_f

题目大意

有 $N$ 个猫塔从左到右排成一行，第 $i$ 座塔高 $P_i$，且 $P$ 是 $1\sim N$ 的一个排列。两塔之间距离定义为坐标之差的绝对值 $|i-j|$。猫初始在高度 $N$ 的塔顶。

可以反复选择并移除塔。移除塔时猫的行为如下：

• 若移除的不是猫所在塔，猫不动；
• 若移除的是猫所在塔，且该塔左/右侧还有相邻塔，则猫跳到"从当前位置只沿相邻塔移动所能到达的塔中最高的一座"（去掉被移除的那座），移动距离为两塔坐标差；
• 若移除猫所在塔时其左右都没有相邻塔，猫跳进怀抱，游戏结束。

注意：被移走的塔留下的空隙不会被填补，即塔的相邻关系始终是初始时的左右邻居。求在游戏结束前，猫移动总距离的最大值。

思路

这是本场最有难度的一道题，核心是把过程归约到笛卡尔树上的树形 DP。

第 1 步：状态与关键不变式。 记状态 $(i,l,r)$ 表示"猫在塔 $i$ 上，且当前仍立着、从 $i$ 出发沿相邻关系可达的塔恰好是连续区间 $[l,r]$"（$l\le i\le r$）。关键不变式是：猫在塔 $i$ 上时，$[l,r]$ 内所有塔的高度都不超过 $P_i$。理由：猫最初在全局最高的塔上，而它每次落脚的都是"当前可达区间中最高的塔"，之后区间的收缩（移除塔）不会破坏这一性质。

第 2 步：定义区间 $[L_i,R_i]$。 对每个塔 $k$，定义 $[L_k,R_k]$ 为包含 $k$ 的最大区间，使得其中所有塔高 $\le P_k$，即左右分别被最近的更高塔挡住：

• $L_k$：若左侧存在 $i<k$ 且 $P_i>P_k$，则 $L_k$ 等于最大的这样的 $i$ 加 $1$，否则 $L_k=1$；
• $R_k$：对称地，若右侧存在 $j>k$ 且 $P_j>P_k$，则 $R_k$ 等于最小的这样的 $j$ 减 $1$，否则 $R_k=N$。

由不变式可知，任何从初始状态可达的状态 $(i,l,r)$ 都满足 $[l,r]\subseteq[L_i,R_i]$。

第 3 步：归约到状态 $S_i=(i,L_i,R_i)$。 从 $S_i$ 出发，我们可以先把 $[L_i,R_i]\setminus[l,r]$ 中的塔全部移除（猫不动，移动距离不增加），从而到达 $(i,l,r)$。因此

$$dp[(i,L_i,R_i)] \ge dp[(i,l,r)],$$

其中 $dp(\cdot)$ 表示从该状态到游戏结束的最大移动距离。于是只需考虑状态 $S_i$。

第 4 步：只保留两种转移。 在状态 $S_i$ 中，若要猫移动，必须移除塔 $i$，猫会跳到"剩余可达塔中最高的那座" $j$。可行的 $j$ 必须满足：$j\in[L_i,R_i]$，且 $i$ 与 $j$ 之间的塔（不含 $i,j$ 本身）高度都不超过 $P_j$（否则 $j$ 不是剩余塔中最高的）。

可以证明：只需考虑每侧最高的塔：

$$M^L_i=\text{区间 }[L_i,\ i-1]\text{ 中最高的塔},\qquad M^R_i=\text{区间 }[i+1,\ R_i]\text{ 中最高的塔}.$$

理由如下（以左侧为例）。先验证两个事实：

• 若 $j< i$ 是可行的转移目标，则 $j\in[L_{M^L_i},\ R_{M^L_i}]$。这是因为 $M^L_i$ 是 $[L_i,i-1]$ 中的最高塔，而 $[M^L_i,i-1]$ 内所有塔都不高于 $P_{M^L_i}$，且 $P_i>P_{M^L_i}$，从而 $L_{M^L_i}=L_i$、$R_{M^L_i}=i-1$。
• 从 $S_{M^L_i}$ 出发，可以"收缩区间"到达 $S_j$（不断移除不包含 $j$ 那一侧的塔、移走当前塔，沿笛卡尔树一步步逼近 $j$），于是 $dp(S_{M^L_i})\ge dp(S_j)+d$，其中 $d$ 为移动距离之和，由三角不等式知 $d\ge |M^L_i-j|$。

于是对任意左侧可行目标 $j$ 有

$$dp(S_j)+(i-j)\ \le\ dp(S_{M^L_i})-(M^L_i-j)+(i-j)\ \le\ dp(S_{M^L_i})+(i-M^L_i),$$

即 $j$ 的方案不会优于 $M^L_i$ 的方案；右侧同理。所以 DP 转移只需考虑 $M^L_i$ 与 $M^R_i$ 两个方向：

$$dp(S_i)=\max\Big(dp(S_{M^L_i})+|i-M^L_i|,\ dp(S_{M^R_i})+|i-M^R_i|\Big),$$

当 $M^L_i$ 或 $M^R_i$ 不存在时忽略对应项；若 $L_i=R_i=i$（没有任何可达的其他塔），则 $dp(S_i)=0$。

第 5 步：这就是笛卡尔树。 如果对每个 $i$ 连边 $i\to M^L_i$、$i\to M^R_i$（存在时），得到的图恰好是一棵最大笛卡尔树：每个节点的高度大于其子节点高度，根是高度 $N$ 的塔 $k_0$，且 $i$ 的左子/右子分别是其区间内左侧/右侧的最高塔。可以借助单调栈在 $O(N)$ 时间内构建：

从左到右扫描每个 i：
    当栈顶元素高度小于 P_i 时：栈顶出栈，最后一个出栈的成为 i 的左子；
    若栈仍非空：栈顶成为……（i 成为栈顶的右子）；
    把 i 入栈。

第 6 步：树形 DP。 设 $dp[i]$ 表示 $dp(S_i)$，则

$$dp[i]=\max\big(dp[lc_i]+(i-lc_i),\ dp[rc_i]+(rc_i-i)\big),$$

其中 $lc_i,rc_i$ 为 $i$ 的左、右子（不存在时忽略）。答案为 $dp[k_0]$。由于边总是从较高塔指向较低塔，可以按高度从小到大处理，从而避免递归爆栈。

样例 1 演算：$P=[5,3,4,1,2]$，根为塔 $1$。区间 $[L_i,R_i]$ 与笛卡尔树如下：塔 $1$（高 $5$）的右子是塔 $3$（高 $4$，$[2,5]$ 中最高）；塔 $3$ 的左子是塔 $2$（高 $3$）、右子是塔 $5$（高 $2$）；塔 $5$ 的左子是塔 $4$（高 $1$）。叶子 $dp_2=dp_4=0$，$dp_5=dp_4+1=1$，$dp_3=\max(dp_2+1,\ dp_5+2)=3$，$dp_1=dp_3+2=5$，答案 $5$，与样例一致。

参考代码

#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), pos(n + 1);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        pos[a[i]] = i; // 高度 -> 位置
    }

    // 构建最大笛卡尔树（高度更大的节点在更上层）
    vector<int> lc(n, -1), rc(n, -1);
    stack<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) {
            lc[i] = st.top(); // 最后弹出的成为 i 的左子
            st.pop();
        }
        if (!st.empty()) rc[st.top()] = i; // i 成为栈顶的右子
        st.push(i);
    }

    // 树形 DP：子节点高度更小，按高度从小到大处理即可避免递归
    vector<long long> dp(n, 0);
    for (int h = 1; h <= n; h++) {
        int i = pos[h];
        if (lc[i] != -1) dp[i] = max(dp[i], dp[lc[i]] + (long long)(i - lc[i]));
        if (rc[i] != -1) dp[i] = max(dp[i], dp[rc[i]] + (long long)(rc[i] - i));
    }
    cout << dp[pos[n]] << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O(N)$（单调栈建树 + 按高度 DP）
• 空间复杂度：$O(N)$

---

G - Domino Arrangement

题目链接：https://atcoder.jp/contests/abc435/tasks/abc435_g

题目大意

有 $N$ 个格子，编号 $1\sim N$，初始都没有涂色。有 $M$ 种颜色，第 $i$ 种颜色可以给区间 $[L_i,R_i]$ 内的任意多个格子涂色。求满足以下条件的涂色方案数，对 $998244353$ 取模：

对每个涂了色的格子 $i$，$i-1$ 与 $i+1$ 中恰好有一个与它颜色相同（$0$ 和 $N+1$ 视为无色）。

（$N,M\le 5\times 10^5$）

思路

这是本场最难的计数题。核心分三步：把条件翻译成"多米诺覆盖"，建立 DP 递推，再用懒标记把递推批量加速。

第 1 步：条件转化。 考察某一种颜色 $c$ 的任意极大连续段（连续若干个涂成 $c$ 的格子）：

• 长度为 $1$：该格左右邻居都不是 $c$，不满足"恰好一个同色"；
• 长度 $\ge 3$：段中间的格子左右邻居都是 $c$，有 $2$ 个同色邻居，不满足；
• 长度恰好为 $2$：段两端的格子恰好各有一个同色邻居（另一个邻居不是 $c$ 或不存在），满足。

因此，合法涂色方案 $\iff$ 把某些格子配对成互不重叠的长度为 $2$ 的块（多米诺），每个块 $[i-1,i]$ 被赋予一种能同时覆盖这两格的颜色 $c$（即 $L_c\le i-1$ 且 $R_c\ge i$），且相邻两个块不能同色（否则会合并成长度为 $4$ 的段）。记

$$C_i=\{\,c \mid L_c\le i-1\text{ 且 }i\le R_c\,\}$$

为能覆盖格子对 $(i-1,i)$ 的颜色集合。

第 2 步：DP 递推。 令 $dp[i][c]$ 表示"涂色方案中，最右被涂的格子是 $i$ 且颜色为 $c$ 的方案数"。由于 $i$ 是最右被涂格，$i+1$ 必为无色，条件要求 $i-1$ 与 $i$ 同色，故 $[i-1,i]$ 必须是 $c$ 色块，从而 $c\in C_i$；且前 $i-2$ 个格子构成合法涂色、同时 $i-2$ 不能是 $c$ 色（否则段会向左延伸）。于是

$$dp[i][c]=S_{i-2}-dp[i-2][c]\qquad(c\in C_i),$$

其中 $S_k$ 表示前 $k$ 个格子的合法涂色总数。求和得

$$S_k=S_{k-1}+\sum_{c\in C_k}dp[k][c] =S_{k-1}+|C_k|\,S_{k-2}-\sum_{c\in C_k}dp[k-2][c].$$

边界：$S_0=1$（空涂色）、$S_1=1$（只有空涂色）。答案即 $S_N$。

第 3 步：快速计算 $\sum_{c\in C_k}dp[k-2][c]$。 定义数组 $T_k$：对 $c\in C_k$，$T_k[c]=dp[k-2][c]$；否则为"未定义"。那么 $S_k=S_{k-1}+|T_k|\,S_{k-2}-\operatorname{sum}(T_k)$，其中 $|T_k|=|C_k|$，$\operatorname{sum}(T_k)=\sum_{c\in C_k}dp[k-2][c]$。

来看 $T_k$ 与 $T_{k-2}$ 的关系（逐颜色）：

• $c\in C_k\cap C_{k-2}$：$T_k[c]=dp[k-2][c]=S_{k-4}-dp[k-4][c]=S_{k-4}-T_{k-2}[c]$，即整体做"取反再平移"；
• $c\in C_k\setminus C_{k-2}$：由于 $dp[k-2][c]=0$（$c\notin C_{k-2}$），$T_k[c]=0$；
• $c\in C_{k-2}\setminus C_k$：删除该颜色；
• 其余：未定义。

而每个颜色 $c$ 满足 $c\in C_k\iff L_c+1\le k\le R_c$，所以它在 $k$ 轴上是一段连续区间：固定奇偶性后，进入/离开事件各至多一次。全部颜色的进入/离开事件总数是 $O(M)$。

懒标记实现：对每个奇偶性分别维护一个结构，其中每个活跃颜色存一个"存储值" $v_c$，配合全局标记 $mul,add$，使得实际值

$$\text{actual}(c)=mul\cdot v_c+add\pmod{MOD},\quad mul\in\{1,-1\}.$$

"取反再平移" $x\to S_{k-4}-x$ 只需更新标记：

$$mul\leftarrow -mul,\qquad add\leftarrow S_{k-4}-add,$$

$O(1)$ 完成。删除颜色时把它的存储值从 $\sum v$ 中减去、计数减一；加入颜色时令实际值为 $0$（即 $v_c=-add/mul$）、计数加一。这样每步 $k$ 都能以 $O(1)$（事件数摊销）得到 $|C_k|$ 与 $\operatorname{sum}(T_k)$，从而算出 $S_k$。总复杂度 $O(N+M)$。

参考代码

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

const ll MOD = 998244353;

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

    int n, m;
    cin >> n >> m;

    // 颜色 c 活跃于 k 的区间为 [L_c+1, R_c]。
    // 对两种奇偶性分别记录进入/离开事件：enter[p][k]、leave[p][k]
    vector<vector<vector<int>>> enter(2, vector<vector<int>>(n + 3));
    vector<vector<vector<int>>> leave(2, vector<vector<int>>(n + 3));

    for (int c = 0; c < m; c++) {
        int L, R;
        cin >> L >> R;
        int lo = L + 1;
        for (int p = 0; p < 2; p++) {
            int first = lo;
            if ((first & 1) != p) first++;          // 奇偶性为 p 的最小步
            if (first > R) continue;
            int last = R;
            if ((last & 1) != p) last--;            // 奇偶性为 p 的最大步
            enter[p][first].push_back(c);
            leave[p][last + 2].push_back(c);        // 该奇偶性下离开的步
        }
    }

    vector<ll> S(n + 2, 0);
    S[0] = 1; // 空涂色
    if (n >= 1) S[1] = 1;

    // 懒标记：实际值 = mul * val + add  (mul 为 1 或 -1)
    // 注意 val 按 (颜色, 奇偶性) 分开存：同一个颜色可以同时在两个奇偶性的结构中活跃，
    // 且两处的存储值可能不同，必须独立保存。
    vector<ll> mul(2, 1), add(2, 0);
    vector<ll> sumv(2, 0);   // 活跃颜色存储值之和
    vector<ll> cnt(2, 0);    // 活跃颜色个数 = |C_k|
    vector<array<ll, 2>> val(m); // val[c][p]：颜色 c 在奇偶性 p 结构中的存储值
    vector<array<char, 2>> on(m); // on[c][p]：颜色 c 在奇偶性 p 的结构中活跃

    for (int k = 2; k <= n; k++) {
        int p = k & 1;
        if (k >= 4) {
            // 全局变换 x -> S[k-4] - x
            mul[p] = (MOD - mul[p]) % MOD;
            add[p] = (S[k - 4] - add[p] + MOD) % MOD;
        }
        // 离开的颜色
        for (int c : leave[p][k]) {
            if (on[c][p]) {
                on[c][p] = 0;
                cnt[p]--;
                sumv[p] = (sumv[p] - val[c][p] + MOD) % MOD;
            }
        }
        // 进入的颜色：实际值置 0
        for (int c : enter[p][k]) {
            if (!on[c][p]) {
                on[c][p] = 1;
                cnt[p]++;
                val[c][p] = (mul[p] == 1) ? (MOD - add[p]) % MOD : add[p];
                sumv[p] = (sumv[p] + val[c][p]) % MOD;
            }
        }
        ll sumT = (mul[p] * sumv[p] + add[p] * cnt[p]) % MOD;
        // S_k = S_{k-1} + |C_k| * S_{k-2} - sum(T_k)
        S[k] = (S[k - 1] + cnt[p] * S[k - 2] % MOD - sumT) % MOD;
        if (S[k] < 0) S[k] += MOD;
    }

    cout << S[n] << '\n';
    return 0;
}

复杂度分析

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