AtCoder Beginner Contest 438 题解

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

比赛概览

本场 ABC438 难度呈明显的阶梯式上升：A、B 两题属于轻松签到题，C、D 考验基础的栈模拟与前缀和思想；从 E 开始难度明显提升——E 是函数图上的二进制倍增，F 把"路径覆盖"问题转化为按 $k$ 计数的树上统计（需要 LCA），G 则是 $\gcd$ 拆分 + 离线树状数组的数学题。其中 F 的"把 $f(i,j)\ge k$ 转化为覆盖一段最短路径，再增量维护路径端点"的转化，以及 G 的"互素化 + 环形区间拆分 + 离线 $\min$ 求和"是全场最值得反复体会的核心考点。

---

A - First Contest of the Year

题目链接：https://atcoder.jp/contests/abc438/tasks/abc438_a

题目大意

某星球上一年有 $D$ 天，比赛每 $7$ 天举行一次（比赛不跨天）。已知某年第一场比赛在该年第 $F$ 天（$1\le F\le 7$），问下一年第一场比赛落在下一年的第几天。输入 $D,F$，输出一个整数 $N$。

思路

关键观察：比赛固定在每个相差 $7$ 天的日子里举行，所以某年度的比赛日为 $F, F+7, F+14, \ldots$。下一年的第 $x$ 天，等价于本年度的第 $D+x$ 天。因此问题变成：求最小的正整数 $x$，使得第 $D+x$ 天恰好是比赛日，即

$$D + x \equiv F \pmod 7,\qquad 1\le x\le 7.$$

设 $r = (D-F)\bmod 7$，则 $D+x\equiv F \pmod 7 \iff x \equiv F-D \equiv -r \pmod 7$。因此最小正整数解为

$$x = 7 - r = 7 - \big((D-F)\bmod 7\big).$$

这里当 $r=0$ 时 $x=7$（即下一场正好落在下一年的第 $7$ 天），上式恰好给出 $7$，无需特判。

易错点：若直接写 (F - D) % 7 之类的式子，在 C++ 里负数取模结果为负，容易出错；而本题约束 $D\ge 10>F$ 保证了 $D-F>0$，所以 (D - F) % 7 恒为非负，使用安全。更稳妥、也更直观的实现是直接模拟：

while (F <= D) F += 7;   // 把第一场比赛不断往后推，直到越过年末
cout << F - D << '\n';   // 越过的天数就是下一年的第几天

参考代码

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

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

    int D, F;
    cin >> D >> F;
    cout << 7 - (D - F) % 7 << '\n';
    return 0;
}

复杂度分析

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

---

B - Substring 2

题目链接：https://atcoder.jp/contests/abc438/tasks/abc438_b

题目大意

给定数字串 $S$（长度 $N$）和 $T$（长度 $M$）。每次操作可任选 $T$ 中的一位，将其数字加 $1$（若为 9 则变成 0）。求使 $T$ 成为 $S$ 的连续子串所需的最小操作次数。

思路

关键观察：$S$ 的长度为 $M$ 的连续子串一共只有 $N-M+1$ 个，且每个位置的数字可以独立变换。所以最朴素的枚举就足够：对 $S$ 的每一个长度为 $M$ 的子串 $S'$，计算把 $T$ 变成 $S'$ 所需的最小步数，取全局最小值。

逐位代价：设 $T$ 的第 $k$ 位数字为 $x_1$，$S'$ 的第 $k$ 位数字为 $x_2$。由于每次只能把 $x_1$ 加 $1$（逢 $9$ 回 $0$），把 $x_1$ 变成 $x_2$ 的最小步数就是在模 $10$ 意义下从 $x_1$ "前进"到 $x_2$ 的步数：

• 若 $x_1\le x_2$，需 $x_2-x_1$ 步；
• 若 $x_1>x_2$，需 $x_2-x_1+10$ 步。

统一写为 $f(x_1,x_2)=(x_2-x_1)\bmod 10$。注意在 C++ 中负数取模结果为负，所以实现时写成 (x2 - x1 + 10) % 10。

于是把 $T$ 变成子串 $S'$ 的总代价为

$$\sum_{k=1}^{M} f(T_k, S'_k) = \sum_{k=1}^{M} \big((x_2^{(k)} - x_1^{(k)})\bmod 10\big).$$

遍历所有 $N-M+1$ 个起点即可。复杂度 $O(NM)\le 10^4$，绰绰有余。

参考代码

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

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

    int N, M;
    cin >> N >> M;
    string S, T;
    cin >> S >> T;

    int ans = 1 << 30;
    for (int st = 0; st + M <= N; st++) {
        int cost = 0;
        for (int i = 0; i < M; i++) {
            int x = T[i] - '0';          // T 中的数字
            int y = S[st + i] - '0';     // 子串中的数字
            cost += (y - x + 10) % 10;   // 模 10 意义下的前进距离
        }
        ans = min(ans, cost);
    }
    cout << ans << '\n';
    return 0;
}

官方题解亦给出 Python 实现，一并列出：

n, m = map(int, input().split())
s = input()
t = input()
ans = 10**9
for st in range(n - m + 1):
    res = 0
    for i in range(m):
        res += (int(s[st + i]) - int(t[i])) % 10
    ans = min(ans, res)
print(ans)

复杂度分析

• 时间复杂度：$O(NM)$（本题 $N,M\le 100$）
• 空间复杂度：$O(1)$（不计算输入存储）

---

C - 1D puyopuyo

题目链接：https://atcoder.jp/contests/abc438/tasks/abc438_c

题目大意

给定长度为 $N$ 的整数序列 $A$。每次操作可选择一个 $k$（$1\le k\le |A|-3$），若满足 $A_k=A_{k+1}=A_{k+2}=A_{k+3}$，则删除这四个元素，剩余部分按原顺序拼接。操作可进行任意次，求最终序列长度的最小值。

思路

关键观察 1：最终长度与操作顺序无关。 我们来理解这一点。每次操作都严格减少序列长度，所以任何操作序列都必然在有限步内停止。只需要说明"局部分合流"：任意两处可删除的块，无论谁先删，都能得到相同的结果——两处块如果互不相交或仅相邻，删除顺序显然可交换；若两处块重叠，则它们必须同属一串相同元素（如 $xxxxxx$ 中删掉任意连续 4 个 $x$ 都剩下同一串），删完结果也相同。因此任意合法的操作序列最终都会到达同一个"不可再删"的状态，最终长度唯一。

关键观察 2：可以用贪心模拟。 既然顺序无关，就按一种简单确定的顺序模拟：从左到右扫描元素，一旦发现栈顶出现 4 个相同元素就立即删掉。用栈实现：

• 依次把 $A_i$ 压入栈；
• 压入后，若栈顶 4 个元素全部相等，则弹出这 4 个元素。

为什么栈顶检查只需一次即可：栈中任何位置一旦出现 4 连，其"最后一个"元素被压入的瞬间它必然位于栈顶，此时就会被立刻弹出，所以每次压入后只需检查一次栈顶即可。整个过程本质上是标准的括号匹配式模拟（这里是"4 个相同"的匹配），最终栈中剩余元素的个数就是答案。

为什么正确：栈模拟给出的是一个具体的、合法的、一直进行到不能再删的完整操作序列，而由关键观察 1，所有完整操作序列的最终长度相同，所以栈的剩余长度就是最小可能值。

边界情况：$N<4$ 时不可能有任何操作，答案就是 $N$；所有元素互不相同、或无法形成 4 连时同样不会触发删除，模拟自然得到正确结果。

参考代码

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

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

    int N;
    cin >> N;
    vector<int> st;
    for (int i = 0; i < N; i++) {
        int v;
        cin >> v;
        st.push_back(v);
        int sz = (int)st.size();
        if (sz >= 4 && st[sz - 1] == st[sz - 2]
                   && st[sz - 1] == st[sz - 3]
                   && st[sz - 1] == st[sz - 4]) {
            for (int j = 0; j < 4; j++) st.pop_back();
        }
    }
    cout << st.size() << '\n';
    return 0;
}

官方题解给出的 Python 实现：

n = int(input())
q = []
for v in list(map(int, input().split())):
    q.append(v)
    if len(q) >= 4 and q[-1] == q[-2] == q[-3] == q[-4]:
        for i in range(4):
            q.pop()
print(len(q))

复杂度分析

• 时间复杂度：$O(N)$（每个元素入栈一次、最多出栈一次，均为 $O(1)$）
• 空间复杂度：$O(N)$（栈的大小）

---

D - Tail of Snake

题目链接：https://atcoder.jp/contests/abc438/tasks/abc438_d

题目大意

给定三个长度为 $N$ 的整数序列 $A,B,C$。求满足 $1\le x<y<N$ 的整数对 $(x,y)$ 中，下式的最大值：

$$\sum_{i=1}^{x} A_i + \sum_{i=x+1}^{y} B_i + \sum_{i=y+1}^{N} C_i.$$

思路

问题转化：看到"三段分别乘上 $A,B,C$ 的权重求和"，第一反应是用前缀和把它化简。设

$$D_i = \sum_{j=1}^{i} A_j,\qquad E_i = \sum_{j=1}^{i} B_j,\qquad F_i = \sum_{j=1}^{i} C_j \quad(0\le i\le N),$$

约定 $D_0=E_0=F_0=0$。则目标值可写成

$$D_x + (E_y - E_x) + (F_N - F_y) = \underbrace{(D_x - E_x)}_{G_x} + \underbrace{(E_y - F_y)}_{H_y} + F_N.$$

$F_N$ 是与 $x,y$ 无关的常数，因此只需最大化

$$G_x + H_y,\qquad 1\le x<y\le N-1.$$

算法：固定 $y$ 时，最优的 $x$ 是所有小于 $y$ 的 $x$ 中 $G_x$ 最大的那一个。于是从左到右扫描 $y=1,2,\ldots,N-1$，同时维护前缀最大值

$$\mathrm{mx} = \max_{1\le x<y} G_x,$$

每扫到 $y$ 时先用 $\mathrm{mx}+H_y+F_N$ 更新答案，再用 $G_y$ 更新 $\mathrm{mx}$（先更新答案再更新 $\mathrm{mx}$，保证 $x<y$ 严格成立）。边界条件 $x\ge 1$、$x<y$、$y\le N-1$ 由循环范围自然保证。

数值范围：$A_i,B_i,C_i\le 10^6$、$N\le 3\times 10^5$，总和不超过 $9\times 10^{11}$，用 long long 即可。

参考代码

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

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

    int N;
    cin >> N;
    vector<ll> A(N), B(N), C(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < N; i++) cin >> B[i];
    for (int i = 0; i < N; i++) cin >> C[i];

    // 0-indexed 前缀和：D[i] = sum_{0..i-1} A，等等
    vector<ll> D(N + 1), E(N + 1), F(N + 1);
    for (int i = 0; i < N; i++) {
        D[i + 1] = D[i] + A[i];
        E[i + 1] = E[i] + B[i];
        F[i + 1] = F[i] + C[i];
    }

    ll ans = LLONG_MIN;
    ll mxG = LLONG_MIN;               // max_{1 <= x < y} (D_x - E_x)
    for (int y = 1; y <= N - 1; y++) {
        if (mxG != LLONG_MIN)
            ans = max(ans, mxG + (E[y] - F[y]) + F[N]);
        mxG = max(mxG, D[y] - E[y]);
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O(N)$
• 空间复杂度：$O(N)$（前缀和数组）

---

E - Heavy Buckets

题目链接：https://atcoder.jp/contests/abc438/tasks/abc438_e

题目大意

有 $N$ 个人和 $N$ 个桶，人和桶都从 $1$ 到 $N$ 编号。初始时第 $i$ 个人持有桶 $i$，所有桶为空。接下来进行 $10^9$ 次操作，每次操作中 $i=1,\ldots,N$ 同时执行：第 $i$ 个人给他当前持有的每个桶加 $i$ 单位水，然后把这些桶交给第 $A_i$ 个人。桶容量无上限。

回答 $Q$ 个询问：第 $T_i$ 次操作结束后，桶 $B_i$ 中有多少水。

思路

关键观察：每个桶独立运动。 同一个人的所有桶行为完全一致，而不同桶之间互不影响。单独看一个桶：若某时刻它被第 $p$ 人持有，则下一轮它会增加 $p$ 单位水并被移交到第 $A_p$ 人手上。换言之，桶的"持有者"沿着函数图 $p \to A_p$ 前进，且在每一轮离开顶点 $p$ 之前累加 $p$。对询问 $(T,B)$，就是求从 $B$ 出发沿函数图走 $T$ 步所累加的顶点编号之和。

朴素模拟不可行（$T$ 可达 $10^9$），用二进制倍增（binary lifting）。

倍增表：对 $0\le d<30$、$1\le i\le N$ 定义：

• $P_{d,i}$：桶初始在第 $i$ 人手上，经过 $2^d$ 次操作后在第几人手上；
• $Q_{d,i}$：这 $2^d$ 次操作中该桶新增加的水量。

边界：$P_{0,i}=A_i$，$Q_{0,i}=i$（一轮中第 $i$ 人加 $i$ 单位）。合并两半：设 $j=P_{d-1,i}$，前 $2^{d-1}$ 轮结束后桶到第 $j$ 人手上，故

$$P_{d,i}=P_{d-1,j},\qquad Q_{d,i}=Q_{d-1,i}+Q_{d-1,j}.$$

回答询问：从 $\text{person}=B,\ \text{water}=0$ 开始，按 $T$ 的二进制位从低到高枚举 $d$，若第 $d$ 位为 $1$，就模拟这 $2^d$ 轮：

water += Q[d][person];
person = P[d][person];

做完后 water 即为答案。

数值范围：至多 $10^9$ 轮、每轮至多加 $N=2\times 10^5$，总水量 $\le 2\times 10^{14}$，用 long long。

补充：本题还有 $O(N+Q)$ 的做法——把每个 $P_{0,i}=A_i$ 形成的函数图分解成若干"环 + 指向环的树"，对环做前缀和、对树部分预处理"到根的路径和"，再配合树上倍增（level ancestor）回答询问；但二进制倍增实现简单、已足够通过。

参考代码

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

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

    int N, Q;
    cin >> N >> Q;
    vector<int> A(N + 1);
    for (int i = 1; i <= N; i++) cin >> A[i];

    const int LOG = 31;                     // 2^30 > 10^9
    vector<vector<int>> P(LOG, vector<int>(N + 1));
    vector<vector<ll>> W(LOG, vector<ll>(N + 1));

    for (int i = 1; i <= N; i++) {
        P[0][i] = A[i];
        W[0][i] = i;                        // 第 i 人一轮加 i 单位
    }
    for (int d = 1; d < LOG; d++) {
        for (int i = 1; i <= N; i++) {
            int j = P[d - 1][i];
            P[d][i] = P[d - 1][j];
            W[d][i] = W[d - 1][i] + W[d - 1][j];
        }
    }

    while (Q--) {
        ll T;
        int B;
        cin >> T >> B;
        ll water = 0;
        int person = B;
        for (int d = 0; d < LOG; d++) {
            if ((T >> d) & 1) {
                water += W[d][person];
                person = P[d][person];
            }
        }
        cout << water << '\n';
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O((N+Q)\log T)$，其中 $T\le 10^9$，$\log T\approx 30$
• 空间复杂度：$O(N\log T)$（倍增表）

---

F - Sum of Mex

题目链接：https://atcoder.jp/contests/abc438/tasks/abc438_f

题目大意

给定一棵 $N$ 个顶点的树（顶点编号 $0\sim N-1$）。对 $0\le i,j<N$ 定义 $f(i,j)$：若路径 $i\to j$ 不包含所有顶点，则 $f(i,j)$ 等于不在该路径上的顶点中最小的编号；若路径包含全部顶点，则 $f(i,j)=N$。求

$$\sum_{0\le i\le j<N} f(i,j).$$

思路

计数转换（把"最小值"换成计数）。按值计数是处理 mex 类问题的经典套路：

$$f(i,j) = \sum_{k\ge 1} \big[\,f(i,j)\ge k\,\big].$$

设 $c_k$ 为满足 $f(i,j)\ge k$ 的配对 $(i,j)$（$i\le j$）的个数，则答案是 $\sum_{k=1}^{N} c_k$。而

$$f(i,j)\ge k \iff \text{路径 } i\to j \text{ 包含顶点 } 0,1,\ldots,k-1 \text{ 的全部}.$$

（若路径不含某个 $v<k$，则 $f(i,j)\le v<k$；反过来若路径包含全部 $0..k-1$，则最小未覆盖编号至少为 $k$。）

关键观察：包含一堆顶点 $\iff$ 包含一段"最短路径"。 设顶点集 $\{0,1,\ldots,k-1\}$ 的最小连通子图为 $T_k$。若 $T_k$ 是一条路径，取它的两个端点 $X_k,Y_k$，则"路径 $i\to j$ 包含全部 $0..k-1$"等价于"路径 $i\to j$ 包含路径 $X_k\to Y_k$"。若 $T_k$ 不是一条路径（形如 Y 形分叉），则根本不存在任何路径能同时覆盖这些顶点，此时 $c_k=0$ 且之后所有 $c_j=0$。

增量维护端点 $(X_k,Y_k)$。初始 $k=1$ 时只有顶点 $0$，$X_1=Y_1=0$。假设已维护好覆盖 $\{0,\ldots,k-2\}$ 的 $(X_{k-1},Y_{k-1})$，加入新顶点 $z=k-1$：

• 若 $Y_{k-1}$ 在路径 $X_{k-1}\to z$ 上，说明 $z$ 挂在 $Y$ 那一侧之外，新端点为 $(X_{k-1}, z)$；
• 否则若 $X_{k-1}$ 在路径 $z\to Y_{k-1}$ 上，说明 $z$ 挂在 $X$ 那一侧之外，新端点为 $(z, Y_{k-1})$；
• 否则 $z$ 落在路径中间的"分支"上，$T_k$ 不是路径，终止。

判定"点 $b$ 是否在路径 $a\to c$ 上"用 LCA 与距离：$b$ 在路径 $a\to c$ 上 $\iff \mathrm{dist}(a,c)=\mathrm{dist}(a,b)+\mathrm{dist}(b,c)$。

计算 $c_k$：即统计有多少对 $i\le j$ 使路径 $i\to j$ 覆盖整条路径 $X_k\to Y_k$。设从 $X$ 出发朝向 $Y$ 的第一条边为 $e_X$，割掉 $e_X$ 后含 $X$ 的连通块大小为 $S_X$；对称地从 $Y$ 方向割掉第一条边得到 $S_Y$。则路径 $i\to j$ 覆盖 $X\to Y$ 当且仅当 $i$ 落在 $X$ 侧、$j$ 落在 $Y$ 侧，故

$$c_k = S_X \cdot S_Y.$$

用子树大小快速求 $S_X,S_Y$（以 $0$ 为根）：设 $l=\mathrm{LCA}(X,Y)$。

• 若 $l=X$（$X$ 是 $Y$ 的祖先）：设 $c$ 为 $Y$ 方向在 $X$ 下的那个孩子，则 $S_X=\mathrm{sz}[X]-\mathrm{sz}[c]$，$S_Y=\mathrm{sz}[Y]$；
• 若 $l=Y$：对称地 $S_X=\mathrm{sz}[X]$，$S_Y=\mathrm{sz}[Y]-\mathrm{sz}[c]$；
• 否则：$S_X=\mathrm{sz}[X]$，$S_Y=\mathrm{sz}[Y]$。

其中"$X$ 下方朝向 $Y$ 的孩子"可用二进制上跳求（把 $Y$ 上升到深度 $\mathrm{dep}[X]+1$ 处的祖先）。

特殊情形 $X_k=Y_k$：只发生在 $k=1$（端点集仅含顶点 $0$）。此时统计"路径含顶点 $0$"的对数 = 总对数 $-$ "两端点落在 $T-\{0\}$ 同一连通块"的对数。设去掉 $0$ 后各连通块大小为 $s_1,\ldots,s_d$，则

$$c_1 = \frac{N(N+1)}{2} - \sum_{t=1}^{d} \frac{s_t(s_t+1)}{2}.$$

答案可能很大：$c_k\le \frac{N(N+1)}{2}$，总答案约 $O(N^3)$，用 long long。

参考代码

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

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

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

    // 倍增 LCA、深度、子树大小、欧拉序
    int LOG = 0;
    while ((1 << LOG) <= N) LOG++;
    vector<int> depth(N), tin(N), tout(N);
    vector<ll> sz(N);
    vector<vector<int>> up(LOG, vector<int>(N));

    int timer = 0;
    auto dfs = [&](auto&& self, int u, int p) -> void {
        tin[u] = timer++;
        up[0][u] = p;
        for (int d = 1; d < LOG; d++) up[d][u] = up[d - 1][up[d - 1][u]];
        sz[u] = 1;
        for (int v : g[u]) {
            if (v == p) continue;
            depth[v] = depth[u] + 1;
            self(self, v, u);
            sz[u] += sz[v];
        }
        tout[u] = timer++;
    };
    dfs(dfs, 0, 0);

    auto isAnc = [&](int a, int b) {
        return tin[a] <= tin[b] && tout[b] <= tout[a];
    };
    auto lca = [&](int a, int b) {
        if (isAnc(a, b)) return a;
        if (isAnc(b, a)) return b;
        for (int d = LOG - 1; d >= 0; d--)
            if (!isAnc(up[d][a], b)) a = up[d][a];
        return up[0][a];
    };
    auto dist = [&](int a, int b) {
        int l = lca(a, b);
        return depth[a] + depth[b] - 2 * depth[l];
    };
    auto onPath = [&](int a, int b, int c) {   // b 在路径 a->c 上?
        return dist(a, c) == dist(a, b) + dist(b, c);
    };
    auto ancestorAt = [&](int v, int dep) {    // v 的深度为 dep 的祖先
        int d = depth[v] - dep;
        for (int i = 0; d; i++) {
            if (d & 1) v = up[i][v];
            d >>= 1;
        }
        return v;
    };

    // 统计路径包含 X->Y 的 (i,j), i<=j 的对数
    auto countPairs = [&](int X, int Y) -> ll {
        if (X == Y) {   // 仅 k=1：路径含顶点 X
            ll total = 1LL * N * (N + 1) / 2;
            ll bad = 0;
            for (int w : g[X]) {
                ll comp = isAnc(w, X) ? (ll)N - sz[X] : sz[w];
                bad += comp * (comp + 1) / 2;
            }
            return total - bad;
        }
        int l = lca(X, Y);
        ll sx, sy;
        if (l == X) {
            int c = ancestorAt(Y, depth[X] + 1);
            sx = sz[X] - sz[c];
            sy = sz[Y];
        } else if (l == Y) {
            int c = ancestorAt(X, depth[Y] + 1);
            sx = sz[X];
            sy = sz[Y] - sz[c];
        } else {
            sx = sz[X];
            sy = sz[Y];
        }
        return sx * sy;
    };

    ll ans = 0;
    int X = 0, Y = 0;                       // 覆盖 {0} 的端点
    for (int k = 1; k <= N; k++) {
        if (k == 1) {
            X = Y = 0;
        } else {
            int z = k - 1;
            if (onPath(X, Y, z)) Y = z;         // Y 在路径 X->z 上
            else if (onPath(z, X, Y)) X = z;    // X 在路径 z->Y 上
            else break;                          // 无法再覆盖，c_k=0 起全部为 0
        }
        ans += countPairs(X, Y);
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O(N\log N)$（每次增量检查 $O(\log N)$，共 $N$ 次；LCA 预计算 $O(N\log N)$）
• 空间复杂度：$O(N\log N)$（倍增表）

---

G - Sum of Min

题目链接：https://atcoder.jp/contests/abc438/tasks/abc438_g

题目大意

给定整数 $N,M,K$，以及长度分别为 $N,M$ 的序列 $A,B$。求

$$\sum_{i=0}^{K-1} \min(A_{i\bmod N},\ B_{i\bmod M}) \pmod{998244353},$$

其中 $K$ 可达 $10^{18}$。

思路

直接枚举 $i$ 是不可能的（$K$ 太大），必须利用周期性。整个问题的核心是：把"双周期取 $\min$"的求和，化简成若干"单数组上的区间 $\min$ 求和"询问，再用离线数据结构批量回答。

第一步：按 $\gcd(N,M)$ 分组。 设 $g=\gcd(N,M)$。注意 $i\bmod N\equiv i\bmod M\pmod g$，所以 $i\bmod g$ 相同的所有项可以合并成独立子问题。对每个余数 $r\in[0,g)$：

• 令 $N'=N/g,\ M'=M/g$（此时 $\gcd(N',M')=1$）；
• 取子序列 $A'_t=A_{r+gt}$、$B'_t=B_{r+gt}$（长度分别为 $N',M'$）；
• 满足 $i\equiv r\pmod g$ 且 $i<K$ 的项数为 $K_r=\left\lfloor\dfrac{K-1-r}{g}\right\rfloor+1$（若 $r\ge K$ 则为 $0$，跳过）。

此时每个子问题都满足 $\gcd(N',M')=1$，且形式不变：求 $\sum_{j=0}^{K_r-1}\min(A'_{j\bmod N'},B'_{j\bmod M'})$。

第二步：固定 $A$ 的下标分组，把 $B$ 重排成"连续区间"。 对固定 $k\in[0,N')$，满足 $j\equiv k\pmod{N'}$ 的项为 $j=k+cN'$（$c=0,1,\ldots,\mathrm{cnt}_k-1$），其中

$$\mathrm{cnt}_k=\left\lfloor\frac{K_r-1-k}{N'}\right\rfloor+1.$$

这些项的 $A$ 下标恒为 $k$，而 $B$ 的下标为 $(k+cN')\bmod M'$。因为 $\gcd(N',M')=1$，$N'$ 在模 $M'$ 下存在逆元 $\mathrm{inv}$（扩展欧几里得求出），于是

$$(k+cN')\bmod M' \equiv N'\big((\mathrm{inv}\cdot k+c)\bmod M'\big) \pmod{M'}.$$

定义重排后的序列 $B''_t = B'_{(N't\bmod M')}$，则该组贡献为

$$\sum_{c=0}^{\mathrm{cnt}_k-1} \min\!\Big(A'_k,\ B''_{((s+c)\bmod M')}\Big),\qquad s=\mathrm{inv}\cdot k\bmod M'.$$

即：在 $B''$ 上，从位置 $s$ 开始、长度为 $\mathrm{cnt}_k$ 的环形区间求 $\min$ 之和。

第三步：环形区间拆成"整圈 + 线性区间"。 令 $\mathrm{cnt}_k = qM' + \mathrm{rem}$。整圈的贡献为 $q\cdot \mathrm{AllMin}(x)$，其中

$$\mathrm{AllMin}(x)=\sum_{c=0}^{M'-1}\min(x,B''_c),$$

把 $B''$ 排序后配前缀和，$\mathrm{AllMin}(x)$ 可二分 $O(\log M')$ 求出。余下的长度为 $\mathrm{rem}<M'$ 的环形区间，至多拆成两个线性区间 $[l,r)$（若 $s+\mathrm{rem}\le M'$ 则只拆成一段）。于是问题归约为：

对若干询问 $(l,r,x)$，求 $\sum_{c=l}^{r-1}\min(x,B''_c)$。

第四步：离线回答线性区间询问。 注意

$$\min(x,v)= \begin{cases} v, & v\le x,\\ x, & v>x. \end{cases}$$

把全部询问按 $x$ 升序排序，同时把 $B''$ 的各位置按值升序逐个插入两个树状数组（一个维护个数、一个维护和）。处理到某个 $x$ 时，树状数组中恰好是所有 $\le x$ 的值，于是

$$\sum_{c=l}^{r-1}\min(x,B''_c)=\big(\text{区间内 } \le x \text{ 的值的和}\big)+x\cdot\big(\text{区间长度}-\text{区间内 }\le x\text{ 的个数}\big),$$

两次区间查询 $O(\log M')$ 即可。全部子问题的询问总数不超过 $2\sum N'=2N$，所以总复杂度为 $O(N\log N+M\log M)$ 级别。

易错点：$K$ 用 long long；$q\cdot \mathrm{AllMin}(x)$ 的乘积先取模再乘；所有累加都 $\bmod 998244353$。

参考代码

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

const ll MOD = 998244353;

// 扩展欧几里得：求 a 在模 mod（与 a 互素）下的逆元
ll extgcd(ll a, ll b, ll& x, ll& y) {
    if (b == 0) { x = 1; y = 0; return a; }
    ll x1, y1;
    ll g = extgcd(b, a % b, x1, y1);
    x = y1;
    y = x1 - (a / b) * y1;
    return g;
}
ll modInv(ll a, ll mod) {
    ll x, y;
    extgcd(a, mod, x, y);
    x %= mod;
    if (x < 0) x += mod;
    return x;
}

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

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

    int N, M;
    ll K;
    cin >> N >> M >> K;
    vector<ll> A(N), B(M);
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < M; i++) cin >> B[i];

    ll ans = 0;
    int g = std::gcd(N, M);
    int Np = N / g, Mp = M / g;

    for (int r = 0; r < g; r++) {
        if (r >= K) continue;
        ll Kr = (K - 1 - r) / g + 1;                 // i ≡ r (mod g) 的项数
        vector<ll> Ap, Bp;
        for (int t = r; t < N; t += g) Ap.push_back(A[t]);
        for (int t = r; t < M; t += g) Bp.push_back(B[t]);

        // B2[t] = Bp[(Np * t) mod Mp]
        vector<ll> B2(Mp);
        for (int t = 0; t < Mp; t++) B2[t] = Bp[(ll)Np * t % Mp];

        // AllMin(x) = sum_c min(x, B2[c])，用排序 + 前缀和
        vector<ll> sortedV = B2;
        sort(sortedV.begin(), sortedV.end());
        vector<ll> pref(Mp + 1, 0);
        for (int i = 0; i < Mp; i++) pref[i + 1] = pref[i] + sortedV[i];
        auto allMin = [&](ll x) -> ll {
            int pos = upper_bound(sortedV.begin(), sortedV.end(), x) - sortedV.begin();
            return (pref[pos] + x * (Mp - pos)) % MOD;
        };

        ll invN = (Mp > 1) ? modInv(Np, Mp) : 0;

        struct Query { int l, r; ll x; };
        vector<Query> qs;
        ll sub = 0;

        for (int k = 0; k < Np; k++) {
            if (k > Kr - 1) continue;
            ll cnt = (Kr - 1 - k) / Np + 1;          // 属于该分组的项数
            ll x = Ap[k];
            ll s = (ll)invN * k % Mp;                 // B2 上的起始位置
            ll full = cnt / Mp, rem = cnt % Mp;
            sub = (sub + (full % MOD) * allMin(x)) % MOD;   // 整圈部分
            if (rem > 0) {                            // 余数环形区间 -> 至多两个线性区间
                if (s + rem <= (ll)Mp) qs.push_back({(int)s, (int)(s + rem), x});
                else {
                    qs.push_back({(int)s, Mp, x});
                    qs.push_back({0, (int)(s + rem - Mp), x});
                }
            }
        }

        // 离线：询问按 x 升序，值 <= x 的 B2 逐个插入两个 BIT
        sort(qs.begin(), qs.end(), [](const Query& a, const Query& b) { return a.x < b.x; });
        vector<pair<ll, int>> byVal(Mp);
        for (int i = 0; i < Mp; i++) byVal[i] = {B2[i], i};
        sort(byVal.begin(), byVal.end());

        BIT cntBit(Mp), sumBit(Mp);
        int ptr = 0;
        for (auto& q : qs) {
            while (ptr < Mp && byVal[ptr].first <= q.x) {
                cntBit.add(byVal[ptr].second, 1);
                sumBit.add(byVal[ptr].second, byVal[ptr].first % MOD);
                ptr++;
            }
            ll c = cntBit.range(q.l, q.r);   // 区间内 <= x 的个数
            ll s = sumBit.range(q.l, q.r);   // 区间内 <= x 的值的和
            sub = (sub + s + (q.x % MOD) * ((q.r - q.l) - c)) % MOD;
        }

        ans = (ans + sub) % MOD;
    }

    cout << ans << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O\big((N+M)\log(N+M)\big)$。其中各子问题的 $B''$ 排序合计 $O(M\log M)$，询问总数 $\le 2N$，每询问两次 BIT 查询 $O(\log M')$，合起来 $O(N\log N+M\log M)$。
• 空间复杂度：$O(N+M)$

---

（全文完）