AtCoder Beginner Contest 465 题解

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

AtCoder Beginner Contest 465 题解

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

比赛概览

本场整体难度中等偏上，A、B 两题为纯签到，主要考察基本的不等式比较与循环求和。C 题的关键是把"翻转前 $k$ 项"等价改写为"末尾追加 $k$ 再整体翻转"，用一个奇偶计数器做到线性；D 题把操作看成树上"走边"，贪心让较大的数往上爬即可；E 是经典数位 DP，状态中额外记录"已用数字集合"与"模 $3$ 余数"，重点是前导零的处理；F 是 $6$ 维前缀和（zeta 变换）配合容斥；G 是全场最有区分度、转化链最长的题目，需要把答案分解成 $c_x \cdot d_x$ 的加权和，用环形区间维护 $d_x$ 、用 floor_sum 维护 $c_x$ 的区间和，还包含"全满/缺一个"两个特殊情形，值得反复咀嚼。建议重点掌握 C 的"追加 + 翻转"改写、D 的树形贪心、E 的数位 DP 状态设计，以及 G 的答案分解与容斥思想。

A - Supermajority

题目链接：https://atcoder.jp/contests/abc465/tasks/abc465_a

题目大意

给定正整数 $A, B$ ，若 $A > B \times \frac{2}{3}$ 则输出 Yes，否则输出 No。所有数满足 $1 \le A, B \le 1000$ 。

思路

这是一个非常直接的比较题，唯一的坑是不要用浮点数去算 $B \times \frac{2}{3}$ 。浮点数存在表示误差，虽然本题数据小、直接比较也不容易出错，但更稳妥、更通用的做法是交叉相乘化为整数比较：

A > B \times \frac{2}{3} \iff 3A > 2B.

两边同乘 $3$ 得到的 $3A > 2B$ 是严格等价的整数不等式，比较对象从"实数"变成"整数"，完全避免精度问题。本题数据范围极小（ $3A \le 3000$ 、 $2B \le 2000$ ），连 int 溢出都不会发生。

官方题解还给出了另一种等价的写法：因为 $A$ 是整数，所以

A > \frac{2B}{3} \iff A > \left\lfloor \frac{2B}{3} \right\rfloor,

即直接用整除也能得到正确答案。

易错点：题目要求的是严格大于（>），注意样例 3： $666$ 与 $999 \times \frac{2}{3} = 666$ 相等，因此输出 No。

参考代码

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

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

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

    // A > B*2/3  <=>  3A > 2B，用整数比较避免浮点误差
    cout << (3 * A > 2 * B ? "Yes" : "No") << '\n';
    return 0;
}

复杂度分析

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

B - Parking 2

题目链接：https://atcoder.jp/contests/abc465/tasks/abc465_b

题目大意

停车场收费规则：从整点 $L$ 到整点 $R$ 之间的每个小时收费 $X$ ，其余时间段每个小时收费 $Y$ 。一辆车从整点 $A$ 停到整点 $B$ （不跨午夜， $1 \le A < B \le 23$ ），求总费用。

思路

把时间轴切成"第 $h$ 个小时"（从整点 $h$ 到整点 $h+1$ ），每个小时独立计价。第 $h$ 个小时落在优惠时段内当且仅当

L \le h \le R - 1.

于是只需枚举 $h = A, A+1, \dots, B-1$ ，按上述条件累加 $X$ 或 $Y$ 即可。

关键观察： $A, B, L, R$ 都是整数，且停在整点，所以总时长恰好是 $B - A$ 个小时，不存在"跨小时"的碎片时间段；直接对小时数循环即可，不需要区间求交等复杂处理。

边界情况：

停车区间与优惠区间可能完全不相交（如样例 2， $A=R$ ），此时全部按 $Y$ 计价；
优惠区间也可能完全覆盖停车区间。

参考代码

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

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

    int X, Y, L, R, A, B;
    cin >> X >> Y >> L >> R >> A >> B;

    int sum = 0;
    for (int h = A; h <= B - 1; h++) {
        // 第 h 个小时：从整点 h 到整点 h+1
        if (L <= h && h <= R - 1) sum += X;
        else sum += Y;
    }
    cout << sum << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(B - A) \le O(23)$ ，枚举每个停车小时。
空间复杂度： $O(1)$ 。

C - Reverse Permutation

题目链接：https://atcoder.jp/contests/abc465/tasks/abc465_c

题目大意

给定整数 $N$ 和长度 $N$ 的字符串 $S$ （由 o/x 组成）。初始 $A = (1, 2, \dots, N)$ 。对 $k = 1, 2, \dots, N$ 依次操作：若 $S_k$ 为 o，则翻转 $A$ 的前 $k$ 项；否则什么都不做。求最终序列。 $N \le 5 \times 10^5$ 。

思路

第一步：等价改写操作

直接翻转前 $k$ 项每次都是 $O(k)$ ，整体最坏 $O(N^2)$ ，不可行。关键是要看出一个等价改写：

等价于：维护一个空序列，对 $k = 1..N$ ，先把 $k$ 追加到末尾，若 $S_k$ 为 o 就整体翻转整个序列。

为什么等价？在第 $k$ 步之前，原数组形如

\underbrace{(\text{前 } k-1 \text{ 个元素的某种排列})}_{\text{记为 } P},\ k,\ k+1,\ \dots,\ N.

翻转前 $k$ 项得到的数组是

(k,\ P \text{ 的反序},\ k+1,\ \dots,\ N).

也就是说"前 $k$ 项"这个前缀的演变，只取决于前 $k-1$ 个元素的排列 $P$ ：先让新元素 $k$ 进来（追加到 $P$ 末尾），若需要翻转则整体翻转。所以我们可以只维护长度为 $k$ 的前缀，每步"追加 $k$ + 按需翻转"，这和原操作完全同步。

第二步：用奇偶计数器免去实时翻转

整体翻转是 $O(N)$ 的，若每次都真的翻转仍然太慢。注意到"翻转"只会改变方向，我们可以维护一个虚拟的翻转奇偶性 $c$ ：

当前序列"名义上"被整体翻转了 $c$ 次（只记奇偶）；
当 $c$ 为偶数时，追加 $k$ 就是在"正常方向"的末尾，记入数组 $b$ ；
当 $c$ 为奇数时，序列实际处于倒序，此时在倒序的末尾追加 $k$ ，等价于在正常顺序的开头插入 $k$ ，记入另一个数组 $a$ （按插入顺序收集）；
若 $S_k$ 为 o，把 $c$ 翻转（ $c \gets c \oplus 1$ ）。

处理完全部 $k$ 后：

正常顺序下，前缀元素（按插入顺序存在 $a$ 中）的排布是 a[::-1]，后缀元素（存在 $b$ 中）是 b，所以正常顺序是 a[::-1] + b；
若最终 $c$ 为奇数，再整体反转一次即可。

正确性：每次"追加 + 翻转"都被等价拆成了"按方向追加到对应的一端"，而方向的奇偶性只用 $c$ 一个计数器维护；最终根据 $c$ 决定是否再整体反转，把"欠下"的翻转一次补上。每一步维护的都是真实前缀的某种镜像表示，因此结果与直接模拟一致。

边界情况： $k$ 从 $1$ 到 $N$ ，先判定方向、再决定是否翻转 $c$ （ $c$ 用的是第 $k$ 步之前的状态）。

参考代码

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

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

    int N;
    string S;
    cin >> N >> S;

    vector<int> a, b;    // a: 倒序状态下"追加到虚拟末尾"= 正常顺序的前端；b: 正常顺序的后端
    bool rev = false;    // 虚拟序列当前是否处于倒序
    for (int k = 1; k <= N; k++) {
        if (rev) a.push_back(k);
        else b.push_back(k);
        if (S[k - 1] == 'o') rev = !rev;
    }

    vector<int> ans;
    for (int i = (int)a.size() - 1; i >= 0; i--) ans.push_back(a[i]);
    for (int x : b) ans.push_back(x);
    if (rev) reverse(ans.begin(), ans.end());

    for (int i = 0; i < N; i++) {
        if (i) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';
    return 0;
}

官方题解给出的 Python 参考实现（思路一致）：

n = int(input())
s = input()
a, b = [], []
rev = False
for i in range(n):
    if rev:
        a.append(i + 1)
    else:
        b.append(i + 1)
    if s[i] == "o":
        rev ^= True
ans = a[::-1] + b
if rev:
    ans = ans[::-1]
print(*ans)

复杂度分析

时间复杂度： $O(N)$ ，每个元素至多被处理常数次。
空间复杂度： $O(N)$ ，存储两个辅助数组与答案。

D - X to Y

题目链接：https://atcoder.jp/contests/abc465/tasks/abc465_d

题目大意

给定整数 $X, Y$ 以及 $K \ge 2$ 。变量 $x$ 初始为 $X$ ，每次操作可以把它换成任意满足 $\lfloor x/K \rfloor = y$ 或 $\lfloor y/K \rfloor = x$ 的整数 $y$ 。求把 $x$ 变成 $Y$ 的最少操作次数。共有 $T$ 组数据， $T \le 2\times 10^5$ ， $X, Y, K \le 10^{18}$ 。

思路

第一步：把操作看成树上的走边

考察整数之间的可替换关系： $y = \lfloor x/K \rfloor$ 意味着 $y$ 是" $x$ 的父亲"；反过来， $x$ 是 $y$ 的父亲意味着 $y \in [xK, xK + K - 1]$ ，这些是 $x$ 的"孩子"。因此以 $0$ 为根（注意 $\lfloor 0/K \rfloor = 0$ ， $0$ 是自己的父亲），所有非负整数构成一棵无限 $K$ 叉树，每个节点 $n$ 的父节点是 $\lfloor n/K \rfloor$ 。题目保证总能到达 $Y$ ，而"最少操作次数"就是 $X$ 与 $Y$ 在这棵树上的距离。

第二步：贪心让较大的数往上爬

树的关键性质是：一个节点 $n$ 的孩子都 $\ge nK \ge 2n > n$ （因为 $K \ge 2$ ）。因此若 $x > y$ ，则 $y$ 不可能落在 $x$ 的子树中（子树里所有值都不小于 $x$ ）。于是 $X$ 到 $Y$ 的最短路必然要先让 $x$ 向上走，即做 $x \gets \lfloor x/K \rfloor$ 。

这给出一个非常简单的贪心（类似求 LCA 的"同时上爬"）：

\text{while } X \ne Y:\quad \text{若 } X < Y \text{ 则交换；然后 } X \gets \left\lfloor \frac{X}{K} \right\rfloor,\ \text{ans} \gets \text{ans}+1.

每次让较大的那个数向上走一步。因为每一步最多使较大的数缩小为原来的 $\frac{1}{K}$ ，所以循环次数为 $O(\log_K X + \log_K Y)$ 。

为什么正确：向上走是唯一"减少数值"的操作，而较大的数不可能处于较小数的子树中（见上面的性质），所以较大数向上走这一步必然位于最短路上。两个数交替向上爬，最终在它们的最近公共祖先处相遇，总步数就是树上距离。

边界情况： $X = Y$ 时答案是 $0$ ； $K = 2$ 时向上爬约 $60$ 次即可到达 $0$ 附近，循环必然终止。

参考代码

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

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

    int T;
    cin >> T;
    while (T--) {
        ll X, Y, K;
        cin >> X >> Y >> K;

        ll ans = 0;
        while (X != Y) {
            if (X < Y) swap(X, Y);   // 始终让较大的数向上爬
            X /= K;
            ans++;
        }
        cout << ans << '\n';
    }
    return 0;
}

官方题解给出的 Python 参考实现：

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    x, y, k = map(int, input().split())
    ans = 0
    while x != y:
        if x < y:
            x, y = y, x
        x //= k
        ans += 1
    print(ans)

复杂度分析

时间复杂度： $O\!\left(\frac{\log X + \log Y}{\log K}\right)$ 每组数据； $K \ge 2$ 时每组约 $O(60)$ 。
空间复杂度： $O(1)$ 。

E - Digit Circus

题目链接：https://atcoder.jp/contests/abc465/tasks/abc465_e

题目大意

求 $1 \le x \le N$ 中恰好满足下列三个条件之一的整数个数，对 $998244353$ 取模：

$x$ 是 $3$ 的倍数；
$x$ 的十进制表示中含有数字 3；
$x$ 的十进制表示中恰好出现三种不同的数字。

其中 $N$ 可达 $10^{500}-1$ ，以字符串形式给出。

思路

$N$ 的位数可达 $500$ ，显然要用数位 DP。

状态设计

把所有整数都看成"恰好 $|N|$ 位"，不足的补前导零。需要记录三个信息：

已使用数字的集合 $b$ ：用一个 $10$ 位掩码，第 $d$ 位为 $1$ 表示数字 $d$ 出现过；
当前值模 $3$ 的余数 $m$ ：用来判断条件 1；
是否仍然贴着 $N$ $l$ （tight 标记）： $l=0$ 表示已确定的前缀与 $N$ 的前缀相等， $l=1$ 表示已经小于 $N$ 的前缀。

设 $dp[i][b][m][l]$ 表示处理完前 $i$ 位后的方案数。

转移

填第 $i+1$ 位数字 $d \in \{0,\dots,9\}$ ：

b' = \begin{cases} b, & b = 0 \text{ 且 } d = 0 \quad(\text{前导零不占用数字 } 0),\\ b \mid (1 \ll d), & \text{其他情况}. \end{cases}

m' = (m \cdot 10 + d) \bmod 3.

tight 的转移规则：

若当前 $l = 0$ （贴着 $N$ ）：只能填 $d \le s_i$ （ $s_i$ 是 $N$ 的第 $i+1$ 位数字）；填 $d = s_i$ 时保持 $l=0$ ，填 $d < s_i$ 时变为 $l=1$ ；
若当前 $l = 1$ （已经更小）：任意 $d$ 均可，保持 $l=1$ 。

统计答案

处理完所有位后，对每个非零掩码 $b$ （ $b = 0$ 只对应数 $0$ ，不在 $[1, N]$ 内）统计它满足的条件个数：

条件 1： $m = 0$ ；
条件 2：掩码的第 $3$ 位为 $1$ ；
条件 3： $\mathrm{popcount}(b) = 3$ 。

累加恰好满足一个条件的状态的 $dp$ 值，即得答案。

关键细节与易错点：

前导零：数字 0 只有在它出现在某个非零数字之后才算"用过"。例如 $x = 10$ 按三位看成 010 时，掩码应为 $\{1\}$ 而非 $\{0,1\}$ ——转移中的特殊分支正是处理这一点；
排除 $0$ 本身：统计时从 $b = 1$ 开始，天然排除 $x=0$ ；
单点 0 在数位 DP 中出现在 $b=0$ 的状态里，它不在答案范围内；
模运算在每次转移后取模即可，注意使用 64 位整数。

参考代码

#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);

    string s;
    cin >> s;
    int n = (int)s.size();

    // dp[掩码][模3余数][tight]：滚动数组
    vector<vector<array<ll, 2>>> dp(1 << 10, vector<array<ll, 2>>(3));
    dp[0][0][0] = 1;   // 一位都没处理，掩码 0、余数 0、贴着 N

    for (char ch : s) {
        int si = ch - '0';
        vector<vector<array<ll, 2>>> ndp(1 << 10, vector<array<ll, 2>>(3));
        for (int b = 0; b < (1 << 10); b++) {
            for (int m = 0; m < 3; m++) {
                for (int l = 0; l < 2; l++) {
                    ll cur = dp[b][m][l];
                    if (!cur) continue;
                    for (int d = 0; d <= 9; d++) {
                        // 前导零不占用数字 0
                        int nb = (b == 0 && d == 0) ? 0 : (b | (1 << d));
                        int nm = (m * 10 + d) % 3;
                        if (l == 0) {
                            if (d <= si) {
                                int nl = (d == si) ? 0 : 1;
                                ndp[nb][nm][nl] = (ndp[nb][nm][nl] + cur) % MOD;
                            }
                        } else {
                            ndp[nb][nm][1] = (ndp[nb][nm][1] + cur) % MOD;
                        }
                    }
                }
            }
        }
        dp = move(ndp);
    }

    ll ans = 0;
    for (int b = 1; b < (1 << 10); b++) {      // b = 0 只对应数 0，排除
        int cnt = __builtin_popcount((unsigned)b);
        for (int m = 0; m < 3; m++) {
            for (int l = 0; l < 2; l++) {
                int cond = 0;
                if (m == 0) cond++;              // 3 的倍数
                if (b & (1 << 3)) cond++;        // 含数字 '3'
                if (cnt == 3) cond++;            // 恰好三种不同数字
                if (cond == 1) ans = (ans + dp[b][m][l]) % MOD;
            }
        }
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O\!\left(2^{10} \times 3 \times 2 \times 10 \times |N|\right) = O(2^{10} \cdot |N|)$ ，即约 $3\times 10^7$ 量级。
空间复杂度： $O(2^{10} \times 3 \times 2)$ ，滚动数组常数大小。

F - Sjeltzer?

题目链接：https://atcoder.jp/contests/abc465/tasks/abc465_f

题目大意

冰箱里有 $N$ 瓶饮料，第 $i$ 瓶的 ID 是 $6$ 位数字串 $S_i$ 、大小为 $V_i$ ，所有 $S_i$ 互不相同。有 $Q$ 次询问，每次给出两个 $6$ 位数字串 $x, y$ ，求所有满足"对每一位 $k$ 都有 $x_k \le s_k \le y_k$ "的饮料大小之和。 $N, Q \le 3\times 10^5$ 。

思路

第一步：把 ID 看成 $6$ 维网格上的点

每个 $6$ 位数字串就是一个 $6$ 维的格子坐标，总格子数为 $10^6$ 。先把它编码成一个整数下标：设

\mathrm{idx}(s) = \sum_{k=1}^{6} s_k \cdot 10^{k-1},

（其中 $s_k$ 表示字符串第 $k$ 位的数字），再维护一个数组 zeta：zeta[idx] 初始为该 ID 对应饮料的大小之和（没有则为 $0$ ）。

第二步： $6$ 维前缀和（zeta 变换）

我们希望预处理出 zeta[idx] = "所有满足 $s_k \le \mathrm{idx}_k$ （每一位都不超过）的饮料大小之和"，这样单点查询 $s \le y$ 就是 $O(1)$ 。逐维做前缀和即可：

\text{对第 } b \text{ 维}:\quad \forall \mathrm{idx},\ \text{若 } \mathrm{idx}_b > 0,\ \text{则 } \mathrm{zeta}[\mathrm{idx}] \mathrel{+}= \mathrm{zeta}[\mathrm{idx} - 10^{b-1}].

做完 $6$ 维后，zeta 就成了 $6$ 维前缀和数组，复杂度 $O(6 \times 10^6)$ 。

第三步：容斥处理下界

询问要求 $x_k \le s_k \le y_k$ ，即同时满足"上界 $s_k \le y_k$ "与"下界 $s_k \ge x_k$ "。把下界取反： $s_k \ge x_k$ 等价于 不满足 $s_k \le x_k - 1$ 。

于是合法的 $s$ 集合 = $\{s : s_k \le y_k\}$ 减去"存在某维 $k$ 使得 $s_k \le x_k - 1$ "的部分。用容斥：对每一维 $k$ ，二选一地取上界

\text{bound}_k = \begin{cases} y_k, & k \notin T,\\ x_k - 1, & k \in T, \end{cases}

则询问答案 = $\displaystyle \sum_{T \subseteq \{1,\dots,6\}} (-1)^{|T|} \,\mathrm{zeta}[\text{按 bound 构成的 idx}]$ ，其中若某维 $k \in T$ 且 $x_k = 0$ ，则 $x_k - 1 < 0$ ，该项贡献为 $0$ （直接跳过）。

正确性：这是标准的容斥原理—— $T$ 表示"强制违反下界的维度集合"，容斥系数 $(-1)^{|T|}$ 保证恰好算出"所有维度都满足下界"的和。

边界情况：

若存在 $k$ 使得 $x_k > y_k$ ，合法集合为空，答案是 $0$ ；
$x_k = 0$ 时， $k \in T$ 的项非法，跳过；
zeta 存的是"大小之和"，最多 $N \times 10^9$ ，用 64 位整数。

参考代码

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

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

    const int D = 6;          // 维度
    int pow10[D + 1];
    pow10[0] = 1;
    for (int i = 1; i <= D; i++) pow10[i] = pow10[i - 1] * 10;

    auto toIdx = [&](const string& s) {
        int idx = 0;
        for (int i = 0; i < D; i++) idx += (s[i] - '0') * pow10[i];
        return idx;
    };
    auto digit = [&](int idx, int d) { return (idx / pow10[d]) % 10; };

    int N;
    cin >> N;
    vector<ll> zeta(pow10[D], 0);
    for (int i = 0; i < N; i++) {
        string s;
        ll v;
        cin >> s >> v;
        zeta[toIdx(s)] += v;
    }

    // 逐维做前缀和（zeta 变换）
    for (int b = 0; b < D; b++) {
        for (int idx = 0; idx < pow10[D]; idx++) {
            if (digit(idx, b) > 0) zeta[idx] += zeta[idx - pow10[b]];
        }
    }

    int Q;
    cin >> Q;
    while (Q--) {
        string x, y;
        cin >> x >> y;
        int vx = toIdx(x), vy = toIdx(y);

        bool ok = true;
        for (int i = 0; i < D; i++)
            if (digit(vx, i) > digit(vy, i)) ok = false;
        if (!ok) {
            cout << 0 << '\n';
            continue;
        }

        ll ans = 0;
        for (int mask = 0; mask < (1 << D); mask++) {
            int zidx = 0;
            bool valid = true;
            for (int i = 0; i < D; i++) {
                if (mask >> i & 1) {                 // 这一维取下界 x_i - 1
                    if (digit(vx, i) == 0) { valid = false; break; }
                    zidx += (digit(vx, i) - 1) * pow10[i];
                } else {                             // 这一维取上界 y_i
                    zidx += digit(vy, i) * pow10[i];
                }
            }
            if (!valid) continue;
            if (__builtin_popcount((unsigned)mask) & 1) ans -= zeta[zidx];
            else ans += zeta[zidx];
        }
        cout << ans << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度：预处理 $O(D \cdot 10^D) = O(6 \times 10^6)$ ；每次询问 $O(2^D \cdot D) = O(64 \times 6)$ 。
空间复杂度： $O(10^6)$ ，即 $10^6$ 个 64 位整数。

G - Sum of Mex of Mod of Linear

题目链接：https://atcoder.jp/contests/abc465/tasks/abc465_g

题目大意

给定 $N, M, C, K$ 与长度为 $N$ 的序列 $A$ （ $0 \le A_i < M$ ）。有 $Q$ 次询问，第 $q$ 次把 $A_{i_q}$ 改成 $X_q$ ，然后求

\sum_{k=0}^{K-1} \mathrm{mex}\bigl\{(Ck + A_i) \bmod M : 1 \le i \le N\bigr\},

输出对 $998244353$ 取模。其中 $N, Q \le 2\times 10^5$ ， $M, K \le 10^9$ ， $0 \le C < M$ 。

思路

这是全场最难的一题，转化链很长，我们逐步推导。

第一步：把答案改写为 $\sum_x c_x d_x$

记 $S_k = \{(A_i + Ck) \bmod M : i\}$ 。对任意集合 $S$ ，有

\mathrm{mex}(S) = \sum_{t \ge 0} [\,0,1,\dots,t \subseteq S\,],

因为右边的求和恰好统计了"从 $0$ 开始连续出现了多少个"。

对固定的 $k$ ，值 $t$ 属于 $S_k$ 当且仅当 $(t - Ck) \bmod M \in A$ （这里 $A$ 指互异值构成的集合）。设 $u = (-Ck) \bmod M$ ，则

[\,0,1,\dots,t \subseteq S_k\,] \iff u,\ (u+1)\bmod M,\ \dots,\ (u+t)\bmod M \in A,

即 $u$ 出发的连续段长度至少是 $t+1$ 。定义

$d_x$ ： $x, (x+1)\bmod M, \dots, (x+d_x-1)\bmod M \in A$ 的最大 $d_x$ ，也就是从 $x$ 出发、在环形意义下最长连续落在 $A$ 里的长度（ $x \notin A$ 时 $d_x = 0$ ）；
$c_x$ ：满足 $Ck + x \equiv 0 \pmod M$ 的 $k \in [0, K)$ 的个数。

于是

\mathrm{mex}(S_k) = d_{(-Ck)\bmod M}, \qquad \sum_k \mathrm{mex}(S_k) = \sum_k d_{(-Ck)\bmod M} = \sum_{x=0}^{M-1} c_x\, d_x.

这样我们把"对所有 $k$ 求 mex"变成"对每个 $x$ 数 $c_x$ 、对每个 $x$ 求当前 $d_x$ "，两者相乘求和。 $c_x$ 只由 $C, M, K$ 决定，与询问无关； $d_x$ 则随 $A$ 的修改而改变，且只有 $O(N)$ 个位置 $d_x \ne 0$ 。

第二步：分析 $c_x$ 的结构

$c_x = \#\{k \in [0,K) : Ck + x \equiv 0 \pmod M\}$ 。设 $g = \gcd(C, M)$ ， $M' = M/g$ ， $C' = C/g$ 。同余方程有解当且仅当 $g \mid x$ 。令 $x = gt$ （ $0 \le t < M'$ ），方程化为

C' k \equiv -t \pmod{M'},

解为 $k \equiv k_0 \pmod{M'}$ ，其中 $k_0 = (-t) \cdot (C')^{-1} \bmod M'$ 。于是

c_x = \begin{cases} q + [\,k_0 < r_0\,], & g \mid x,\\ 0, & g \nmid x, \end{cases} \qquad q = \left\lfloor \frac{K}{M'} \right\rfloor,\ \ r_0 = K \bmod M'.

也就是说 $c_x$ 只在 $g$ 的倍数处非零，且在非零处只取两个值 $q$ 或 $q+1$ 。关键集合是" $k_0 < r_0$ 的那些 $t$ "：

\bigl\{t : (-t)(C')^{-1} \bmod M' < r_0\bigr\} = \bigl\{(-C'u) \bmod M' : u \in [0, r_0)\bigr\}.

第三步： $c$ 的区间和（用 floor_sum）

$d_x$ 的修改量都能写成 $c$ 在某个环上的区间和，因此我们需要一个能快速求 $\sum_{x=l}^{r} c_x$ 的黑盒。由于 $c_x$ 只在 $g$ 的倍数处非零：

\sum_{x=l}^{r} c_x = q \cdot \#\{\text{[}l,r\text{] 内 } g \text{ 的倍数}\} + \#\bigl\{u \in [0,r_0) : (-C'u) \bmod M' \in [\lceil l/g\rceil,\ \lfloor r/g\rfloor]\bigr\}.

第一项是简单的整除计数；第二项需要统计一个模线性递推序列落入给定区间的个数。经典做法是把"统计落入 $[L,R]$ "拆成"小于 $R+1$ 减去小于 $L$ "，而

\#\{u \in [0,n) : (au) \bmod m < t\} = n - \sum_{u=0}^{n-1}\left\lfloor\frac{au + m - t}{m}\right\rfloor + \sum_{u=0}^{n-1}\left\lfloor\frac{au}{m}\right\rfloor,

后两项正是标准的 floor_sum（可以用欧几里得式递归在 $O(\log m)$ 内求出，AtCoder Library 内置）。区间和每次调用 $O(\log M)$ 。

第四步：环形连续段上的 $d_x$ 维护

$d_x$ 只与 $A$ 的"互异值构成哪些连续段"有关： $A$ 中的值把环 $[0, M)$ 分成若干极大连续段，段内每个点 $x$ 的 $d_x$ 等于"从 $x$ 到段尾的距离 $+1$ "。

我们用一个有序表维护这些段（起点 $\to$ 终点），并允许至多一段"绕过 $0$ "的段（记作 wrap 段）。下面推导插入/删除单个值时的答案增量。

插入 $v$ （ $v \notin A$ ）。设 $v-1$ 所在的段为 $[L, v-1]$ （长 $\mathrm{len}_1$ ）， $v+1$ 所在段为 $[v+1, R]$ （长 $\mathrm{len}_2$ ）。插入后两段与 $v$ 合并成 $[L, R]$ （长 $\mathrm{len}_1+\mathrm{len}_2+1$ ）：

对 $x \in [L, v-1]$ ： $d_x$ 从 $\mathrm{len}_1 - \mathrm{pos}$ 变为 $\mathrm{len}_1+\mathrm{len}_2+1 - \mathrm{pos}$ ，每个位置恰好增加 $\mathrm{len}_2 + 1$ ；
对 $x = v$ ： $d_v$ 从 $0$ 变为 $\mathrm{len}_2 + 1$ ；
对 $x \in [v+1, R]$ ： $d_x$ 不变。

故增量

\Delta = (\mathrm{len}_2 + 1)\left(\sum_{x \in [L, v-1]} c_x + c_v\right).

删除 $v$ 是插入的逆过程，增量为上式取负，段按对称方式分裂。这些增量只用到 $c$ 的区间和（而非带权和的复杂形式），这正是上一步能派上用场的原因。

需要特判的边界情形：

插入把环"补满"：当 $A$ 已有 $M-1$ 个值、 $v$ 恰是缺失的那个时， $v-1$ 与 $v+1$ 属于同一条 wrap 段，插入后整个环被填满。此时"段结构"退化（ $d_x = M$ 对所有 $x$ ），答案直接为 $\sum_k \mathrm{mex}(S_k) = K \cdot M.$ （全满只可能发生在 $M \le N$ 时。）
从全满删除一个值 $v$ ：此时 $A$ 恰好缺 $v$ ，每个 $S_k$ 缺 $(v + Ck) \bmod M$ ，故 $\mathrm{mex}(S_k) = (v + Ck) \bmod M,$ 答案为 $\displaystyle \sum_{k=0}^{K-1} (v + Ck) \bmod M$ 。利用 $x \bmod M = x - M\lfloor x/M\rfloor$ 可写成闭式： $\sum_{k=0}^{K-1} (w + ck) \bmod M = K w + \frac{cK(K-1)}{2} - M \cdot \mathrm{floor\_sum}(K, M, c, w),$ 其中 $w = v \bmod M$ 、 $c = C \bmod M$ 。

初始化：对初始的互异值集合，从空集开始逐个模拟插入，用增量公式累出初始答案（ $O(N \log N + N \log M)$ ）。

正确性：答案 $\sum_x c_x d_x$ 由第一步严格推导； $d_x$ 的增量公式按段长逐位置核对；插入/删除互为逆过程保证一致性；两个特殊情形独立验证。整体与暴力对拍通过。

参考代码

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

const ll MOD = 998244353;

// 求和 sum_{0<=i<n} floor((a*i+b)/m)，标准 floor_sum（AtCoder Library 版）
ll floor_sum(ll n, ll m, ll a, ll b) {
    ll ans = 0;
    while (true) {
        if (a >= m) {
            ans += (n - 1) * n / 2 * (a / m);
            a %= m;
        }
        if (b >= m) {
            ans += n * (b / m);
            b %= m;
        }
        ll y_max = a * n + b;
        if (y_max < m) break;
        n = y_max / m;
        b = y_max % m;
        swap(m, a);
    }
    return ans;
}

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

    int N;
    ll M, C, K;
    cin >> N >> M >> C >> K;
    vector<ll> A(N);
    map<ll, ll> cnt;                     // 每种数值的出现次数
    for (int i = 0; i < N; i++) {
        cin >> A[i];
        cnt[A[i]]++;
    }

    /* ---------- c_x 的相关预计算 ---------- */
    ll g = std::gcd(C, M);
    ll Mp = M / g;                        // M' = M / gcd(C, M)
    ll Cp = (C / g) % Mp;                 // C'
    ll q = K / Mp, r0 = K % Mp;           // K = q*M' + r0
    ll a = (Mp - Cp % Mp) % Mp;           // a = -C' mod M'
    ll F0 = floor_sum(r0, Mp, a, 0);
    ll invCp = 0;
    if (Mp > 1) {                         // C' 模 M' 的逆元
        ll t = 0, newt = 1, r = Mp, newr = Cp;
        while (newr != 0) {
            ll qq = r / newr;
            tie(t, newt) = make_pair(newt, t - qq * newt);
            tie(r, newr) = make_pair(newr, r - qq * newr);
        }
        invCp = (t % Mp + Mp) % Mp;
    }

    auto c_at = [&](ll v) -> ll {         // 单点 c_v
        if (v % g != 0) return 0;
        ll t = (v / g) % Mp;
        ll k0 = 0;
        if (Mp > 1) k0 = ((Mp - t % Mp) % Mp) * invCp % Mp;
        return q + (k0 < r0 ? 1 : 0);
    };

    // #{u in [0, r0) : (a*u mod Mp) < t}
    auto cntLessThan = [&](ll t) -> ll {
        if (t <= 0) return 0;
        if (t >= Mp) return r0;
        return r0 - floor_sum(r0, Mp, a, Mp - t) + F0;
    };

    // S_c(l, r) = sum_{x=l}^{r} c_x ，0 <= l <= r < M
    auto S_c = [&](ll l, ll r) -> ll {
        if (l > r) return 0;
        ll cntm = (l == 0) ? (r / g + 1) : (r / g - (l - 1) / g);  // g 的倍数个数
        ll L = (l + g - 1) / g, R = r / g;                          // ceil(l/g), floor(r/g)
        if (L > R) return q * cntm;
        if (R >= Mp) R = Mp - 1;
        ll sp = 0;
        if (L <= R) sp = cntLessThan(R + 1) - cntLessThan(L);
        return q * cntm + sp;
    };

    // 从 s 出发向前 len 个值的 c 之和（环形）
    auto sum_len = [&](ll s, ll len) -> ll {
        if (len <= 0) return 0;
        if (len >= M) return K;           // 整圈
        ll e = (s + len - 1) % M;
        if (s <= e) return S_c(s, e);
        else return S_c(s, M - 1) + S_c(0, e);
    };

    /* ---------- 环形连续段的维护 ---------- */
    map<ll, ll> seg;                      // seg[s] = e：段 [s, e]，至多一段 wrap（s > e）
    set<ll> present;                      // A 中当前的互异值集合
    bool is_full = false;                 // A 是否已覆盖 0..M-1 全部值
    ll ans = 0;                           // 当前答案（精确值，最后再取模）

    // 返回包含 v 的段 (s, e)，v 保证在 A 中
    auto find_run = [&](ll v) -> pair<ll, ll> {
        auto it = seg.upper_bound(v);
        if (it != seg.begin()) {
            auto jt = prev(it);
            ll s = jt->first, e = jt->second;
            if (s <= e) {
                if (s <= v && v <= e) return {s, e};
            } else {
                if (v >= s || v <= e) return {s, e};
            }
        }
        ll s = seg.rbegin()->first, e = seg.rbegin()->second;  // wrap 段
        return {s, e};
    };

    auto insert_val = [&](ll v) {
        if (is_full) return;              // 全满时不会发生插入
        bool left = present.count((v - 1 + M) % M) > 0;
        bool right = present.count((v + 1) % M) > 0;
        if (left && right) {
            ll s_L = find_run((v - 1 + M) % M).first;
            ll s_R = (v + 1) % M;
            if (s_L == s_R) {             // 把 wrap 段与自己合并 => 全满
                present.insert(v);
                ans = K * M;
                seg.clear();
                is_full = true;
                return;
            }
            ll e_R = seg[s_R];
            ll len2 = ((e_R - s_R + M) % M) + 1;
            ll len1 = ((v - 1 - s_L + M) % M) + 1;
            ll delta = (len2 + 1) * (sum_len(s_L, len1) + c_at(v));
            ans += delta;
            present.insert(v);
            seg.erase(s_R);
            seg[s_L] = e_R;
        } else if (left) {
            ll s_L = find_run((v - 1 + M) % M).first;
            ll len1 = ((v - 1 - s_L + M) % M) + 1;
            ll delta = sum_len(s_L, len1) + c_at(v);
            ans += delta;
            present.insert(v);
            seg[s_L] = v;
        } else if (right) {
            ll s_R = (v + 1) % M;
            ll e_R = seg[s_R];
            ll len2 = ((e_R - s_R + M) % M) + 1;
            ll delta = (len2 + 1) * c_at(v);
            ans += delta;
            present.insert(v);
            seg.erase(s_R);
            seg[v] = e_R;
        } else {
            ans += c_at(v);
            present.insert(v);
            seg[v] = v;
        }
    };

    auto remove_val = [&](ll v) {
        if (is_full) {                    // 全满 -> 恰好缺 v
            present.erase(v);
            ll w = v % M, c = C % M;
            __int128 sm = (__int128)K * w + (__int128)c * K * (K - 1) / 2
                          - (__int128)M * floor_sum(K, M, c, w);
            ans = (ll)sm;
            seg.clear();
            seg[(v + 1) % M] = (v - 1 + M) % M;
            is_full = false;
            return;
        }
        auto p = find_run(v);
        ll s = p.first, e = p.second;
        ll len = ((e - s + M) % M) + 1;
        ll pos = (v - s + M) % M;
        ll len1 = pos, len2 = len - pos - 1;
        ll delta = (len2 + 1) * (sum_len(s, len1) + c_at(v));
        ans -= delta;
        present.erase(v);
        if (len1 == 0 && len2 == 0) {
            seg.erase(s);
        } else if (len1 == 0) {
            seg.erase(s);
            seg[(v + 1) % M] = e;
        } else if (len2 == 0) {
            seg[s] = (v - 1 + M) % M;
        } else {
            seg[s] = (v - 1 + M) % M;
            seg[(v + 1) % M] = e;
        }
    };

    /* ---------- 初始化：模拟逐个插入互异值 ---------- */
    ll distinct = (ll)cnt.size();
    if (M >= 2 && distinct == M) {        // 初始就全满
        is_full = true;
        ans = K * M;
        for (auto& [v, c] : cnt) present.insert(v);
    } else {
        present.clear();
        for (auto& [v, c] : cnt) insert_val(v);
    }

    /* ---------- 处理询问 ---------- */
    int Q;
    cin >> Q;
    while (Q--) {
        int i;
        ll X;
        cin >> i >> X;
        --i;
        ll old = A[i];
        if (old != X) {
            cnt[old]--;
            if (cnt[old] == 0) {
                cnt.erase(old);
                remove_val(old);
            }
            cnt[X]++;
            if (cnt[X] == 1) insert_val(X);
            A[i] = X;
        }
        cout << (ans % MOD + MOD) % MOD << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度：初始化 $O(N \log N + N \log M)$ ；每次询问涉及至多一次删除加一次插入，每次各需 $O(\log N)$ 的段操作与 $O(\log M)$ 的 floor_sum 区间和，故单次询问 $O(\log N + \log M)$ 。
空间复杂度： $O(N)$ ，用于存储计数、互异值集合与段表。

（完）