AtCoder Beginner Contest 421 题解

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

AtCoder Beginner Contest 421 题解

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

比赛概览

本场 ABC421 整体难度适中：A 是纯签到，B 是简单的模拟，C 是经典的最小相邻交换问题，D 把超大的 RLE 移动序列合并成 $O(M+L)$ 段分别判断，E 是"掷骰子选保留"的概率 DP，F 是链表结构的插入与区间删除求和，G 是差分转化后的最小费用流。较有区分度的是 D、F、G 三题，其中 G 的建流模型（把"区间加 1"转成差分数组上的"搬球"）值得仔细体会。

A - Misdelivery

题目链接：https://atcoder.jp/contests/abc421/tasks/abc421_a

题目大意

大厦有 $N$ 个房间，第 $i$ 号房间住着名字为 $S_i$ 的人。要把收件人为 $Y$ 的包裹送到 $X$ 号房间，判断收件地址是否正确，即判断 $S_X$ 是否等于 $Y$ 。输入第一行为 $N$ ，随后 $N$ 行是各房间住户的名字，最后一行给出 $X$ 与 $Y$ 。若 $S_X=Y$ 输出 Yes，否则输出 No。

思路

签到题，直接读入并按题意比较即可。注意两点：

大多数语言的数组下标从 $0$ 开始，因此应比较 S[X-1] 与 Y。
字符串比较要比较内容：C++ 的 std::string 重载了 ==，可以直接 S[X-1] == Y；而某些语言（如 Java）需要用 equals 而不能用 == 比较引用。

由于 $N \le 100$ 、字符串长度 $\le 10$ ，没有任何复杂度上的顾虑。题目的"易错点"只有下标偏移与字符串比较方式。

参考代码

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

int main() {
    int N;
    cin >> N;
    vector<string> S(N);
    for (int i = 0; i < N; i++) cin >> S[i];

    int X;
    string Y;
    cin >> X >> Y;

    cout << (S[X - 1] == Y ? "Yes" : "No") << '\n';
    return 0;
}

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

N = int(input())
S = [input() for _ in range(N)]
X, Y = input().split()
X = int(X)

print("Yes" if S[X - 1] == Y else "No")

复杂度分析

时间复杂度：读入 $N$ 个字符串， $O(N)$ （字符串总长度为 $O(10N)$ ）。
空间复杂度： $O(N)$ 。

B - Fibonacci Reversed

题目链接：https://atcoder.jp/contests/abc421/tasks/abc421_b

题目大意

对正整数 $x$ ，定义 $f(x)$ 为：把 $x$ 的十进制表示（无前导零）写成字符串，翻转后按十进制重新解释得到的整数。例如 $f(13)=31$ ， $f(10)=1$ （因为 "01" 解释为 $1$ ）。

给定正整数 $X,Y$ ，定义序列 $a_1=X,\ a_2=Y,\ a_i=f(a_{i-1}+a_{i-2})\ (i\ge 3)$ ，求 $a_{10}$ 。

思路

直接按题意模拟即可：从 $i=3$ 循环到 $i=10$ ，每次把 $a_{i-1}+a_{i-2}$ 转成字符串、翻转、再转回整数。C++ 中可用 to_string、reverse、stoll 一行完成；Python 中可用 str、切片 [::-1]、int。

关键易错点：答案可能超过 32 位整数。分析数值的增长速度：设 $D(x)$ 为 $x$ 的十进制位数。两个数之和的位数至多比较大的那个多 $1$ ，而翻转操作不会增加位数（位数至多不变，因为前导零会被去掉），因此

D(a_i) \le \max\bigl(D(a_{i-1}), D(a_{i-2})\bigr) + 1.

初始 $X,Y \le 10^5$ （至多 $6$ 位），经过 $8$ 次递推后位数至多 $6+8=14$ 位，远小于 64 位整数的上限，所以用 long long 是安全的。 $f(x)$ 恒为正整数（翻转后若前导是零，则去掉后仍至少为一位数字），这一点由字符串反转天然满足。

参考代码

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

int main() {
    vector<long long> a(10);
    cin >> a[0] >> a[1];
    for (int i = 2; i < 10; i++) {
        string s = to_string(a[i - 2] + a[i - 1]);
        reverse(s.begin(), s.end());
        a[i] = stoll(s);
    }
    cout << a[9] << '\n';
    return 0;
}

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

a = [0] * 10
a[0], a[1] = map(int, input().split())

for i in range(2, 10):
    s = str(a[i - 2] + a[i - 1])
    a[i] = int(s[::-1])

print(a[9])

复杂度分析

时间复杂度：仅常数次迭代，每次迭代处理至多十几个字符， $O(1)$ 。
空间复杂度： $O(1)$ 。

C - Alternated

题目链接：https://atcoder.jp/contests/abc421/tasks/abc421_c

题目大意

给定一个长度为 $2N$ 的字符串 $S$ ，其中恰好含有 $N$ 个 A 和 $N$ 个 B。一次操作可以交换 $S$ 中两个相邻的字符。求使得 $S$ 中不存在相邻相同字符所需的最少操作次数。 $N \le 5\times 10^5$ 。

思路

关键观察：含有 $N$ 个 A、 $N$ 个 B 且相邻字符两两不同的字符串只有两种：

\texttt{ABABAB}\cdots,\qquad \texttt{BABABA}\cdots.

因此原问题等价于：把 $S$ 变成目标串 $T$ 所需的最少相邻交换次数，对这两种 $T$ 分别计算后取最小值。

接下来考虑把 $S$ 变成某个 $T$ 的最少相邻交换次数。设 $X_k$ 为 $S$ 中第 $k$ 个 A 所在的位置（ $1$ -indexed）， $Y_k$ 为目标串中第 $k$ 个 A 所在的位置。

交换两个相同字符是无用的操作，所以只需考虑 A 与 B 之间的交换。任何一次相邻交换都恰好使一个 A 的位置改变 $1$ ，因此从 $S$ 到 $T$ 至少需要 $\sum_k |X_k - Y_k|$ 次操作。
反过来，可以贪心地让每个 A 向目标位置移动：对满足 $X_k < Y_k$ 的 $k$ 按 $k$ 升序把第 $X_k$ 、 $X_k+1$ 位交换（把 A 向右推），对满足 $X_k > Y_k$ 的 $k$ 按 $k$ 降序把第 $X_k$ 、 $X_k-1$ 位交换（把 A 向左推）。每做一次操作， $\sum_k |X_k - Y_k|$ 恰好减少 $1$ ，故能恰好用 $\sum_k |X_k - Y_k|$ 步完成。

所以最少交换次数就是 $\sum_k |X_k - Y_k|$ （这里的匹配是"第 $k$ 个 A 对第 $k$ 个 A"的稳定匹配，这也是相邻交换问题中的经典结论）。对于两种目标串：

$T=\texttt{ABAB}\cdots$ 时，第 $k$ 个 A 应在 $Y_k=2k-1$ ；
$T=\texttt{BABA}\cdots$ 时，第 $k$ 个 A 应在 $Y_k=2k$ 。

答案为

\min\left\{\sum_k |X_k-(2k-1)|,\ \sum_k |X_k-2k|\right\}.

注意 A 的位置确定了，B 的位置也就确定了（因为有 $N$ 个 B 填满其余位置），因此只需统计 A 即可。一次扫描即可得到所有 $X_k$ ，时间复杂度 $O(N)$ 。总和的数量级为 $N \times 2N = O(N^2)$ ，需用 long long。

参考代码

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

int main() {
    int N;
    string S;
    cin >> N >> S;

    long long ans = (1LL << 62);
    // par = 0 : 目标为 ABAB...，第 k 个 A 应在 2k-1
    // par = 1 : 目标为 BABA...，第 k 个 A 应在 2k
    for (int par = 0; par < 2; par++) {
        long long sum = 0;
        int k = 0;
        for (int i = 0; i < 2 * N; i++) {
            if (S[i] == 'A') {
                k++;
                long long y = 2LL * k - 1 + par;          // 目标位置
                sum += llabs((long long)(i + 1) - y);     // 当前位置 i+1
            }
        }
        ans = min(ans, sum);
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度：对两种目标串各做一次 $O(N)$ 扫描， $O(N)$ 。
空间复杂度： $O(1)$ （只需存储原串）。

D - RLE Moving

题目链接：https://atcoder.jp/contests/abc421/tasks/abc421_d

无限网格上，Takahashi 从 $(R_t,C_t)$ 、Aoki 从 $(R_a,C_a)$ 出发，分别按照长度为 $N$ 的移动串 $S,T$ （仅含 U/D/L/R）同时移动 $N$ 步，每步一格。求"恰在一次移动结束后两人位于同一格子"的次数。由于 $N$ 很大（ $\le 10^{14}$ ）， $S$ 与 $T$ 以 RLE 形式给出： $S$ 由 $M$ 段 $(S'_i,A_i)$ 拼接而成（ $A_i$ 个 $S'_i$ 字符）， $T$ 由 $L$ 段 $(T'_j,B_j)$ 拼接而成，且两串总长度都等于 $N$ 。 $M,L \le 10^5$ 。

思路

方向约定：本题以"向下、向右"为正方向，因此 $U$ 使行坐标 $-1$ ， $D$ 使行坐标 $+1$ ， $L$ 使列坐标 $-1$ ， $R$ 使列坐标 $+1$ 。

子问题 (★)：两人都朝固定方向移动时，如何计数？设某段时间内 Takahashi 从 $(r_1,c_1)$ 出发、每步移动方向向量 $(a,b)$ ，Aoki 从 $(r_2,c_2)$ 出发、方向向量 $(p,q)$ 。走 $t$ 步后两人的位置分别为

(r_1+at,\ c_1+bt),\qquad (r_2+pt,\ c_2+qt).

两人重合当且仅当

(r_1-r_2)+(a-p)t=0,\qquad (c_1-c_2)+(b-q)t=0.

记 $\Delta r=r_1-r_2$ ， $\Delta c=c_1-c_2$ ， $\alpha=a-p$ ， $\beta=b-q$ ，则需求解整数 $t$ 满足

\Delta r+\alpha t=0,\qquad \Delta c+\beta t=0.

分两类讨论：

$\alpha=\beta=0$ （两人同方向）：相对位置不变。若 $\Delta r=\Delta c=0$ ，则整段每走一步两人都重合，计数为段长 $\text{len}$ ；否则整段永不重合。
否则：两个一次方程至多确定一个整数 $t$ 。对每个方程：若系数非零，则 $t=-\Delta r/\alpha$ （需满足整除）；若系数为零，则要求对应差值也为零（否则无解）。两方程给出的 $t$ 必须一致，且落在 $[1,\text{len}]$ 内（ $t$ 从 $1$ 开始，因为初始重合不计），才计 $1$ 次。

合并时间轴：两人同时移动，用双指针把两人的 RLE 段合并处理。维护两人各自的当前段（方向与剩余长度），每轮取 $\text{len}=\min(\text{剩余}_T,\text{剩余}_A)$ ，这一段内两人的方向都是常数，直接调用子问题 (★) 计数；然后两人都沿各自方向前进 $\text{len}$ 步，剩余长度减去 $\text{len}$ ，若某人的剩余长度归零则进入下一段。由于两串总长度都等于 $N$ ，两人会同时耗尽所有段，合并的段数为 $O(M+L)$ 。

易错点：

$U$ 使行坐标减小、 $D$ 使行坐标增大，方向向量不能写反；
$t$ 从 $1$ 开始计数，两人在段起点已经重合不算本段贡献（它已在上一段的末尾被计过）；
判断整除时直接用取模 diff % alpha == 0（负数取模不影响整除性判断）；
坐标数量级可达 $10^9 + 10^{14}$ ，计数总和可达 $10^{14}$ ，一律用 long long。

参考代码

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

using ll = long long;

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

    ll Rt, Ct, Ra, Ca;
    cin >> Rt >> Ct >> Ra >> Ca;
    ll N;
    int M, L;
    cin >> N >> M >> L;

    vector<char> sc(M);
    vector<ll> sn(M);
    for (int i = 0; i < M; i++) cin >> sc[i] >> sn[i];
    vector<char> tc(L);
    vector<ll> tn(L);
    for (int i = 0; i < L; i++) cin >> tc[i] >> tn[i];

    // 方向字符 -> (行增量, 列增量)
    auto vec = [](char c, ll& dr, ll& dc) {
        dr = 0; dc = 0;
        if (c == 'U')      dr = -1;
        else if (c == 'D') dr = 1;
        else if (c == 'L') dc = -1;
        else               dc = 1;   // 'R'
    };

    ll drt, dct, dra, dca;
    vec(sc[0], drt, dct);
    vec(tc[0], dra, dca);
    int pt = 0, pa = 0;
    ll remt = sn[0], rema = tn[0];

    ll ans = 0;
    while (pt < M && pa < L) {
        ll len = min(remt, rema);

        ll dr = Rt - Ra, dc = Ct - Ca;   // 当前行、列差 (Taka - Aoki)
        ll ar = drt - dra, ac = dct - dca;

        ll cnt = 0;
        if (ar == 0 && ac == 0) {
            // 同方向：初始重合则整段重合，否则永不重合
            if (dr == 0 && dc == 0) cnt = len;
        } else {
            bool ok = true;
            ll t1 = 0; bool have1 = false;
            if (ar != 0) {
                if (dr % ar != 0) ok = false;
                else { t1 = -dr / ar; have1 = true; }
            } else {
                if (dr != 0) ok = false;
            }
            ll t2 = 0; bool have2 = false;
            if (ac != 0) {
                if (dc % ac != 0) ok = false;
                else { t2 = -dc / ac; have2 = true; }
            } else {
                if (dc != 0) ok = false;
            }
            if (ok && have1 && have2 && t1 != t2) ok = false;
            if (ok) {
                ll t = have1 ? t1 : t2;
                if (t >= 1 && t <= len) cnt = 1;
            }
        }
        ans += cnt;

        Rt += drt * len; Ct += dct * len;
        Ra += dra * len; Ca += dca * len;
        remt -= len; rema -= len;
        if (remt == 0) { pt++; if (pt < M) { vec(sc[pt], drt, dct); remt = sn[pt]; } }
        if (rema == 0) { pa++; if (pa < L) { vec(tc[pa], dra, dca); rema = tn[pa]; } }
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度：合并后段数为 $O(M+L)$ ，每段 $O(1)$ 判断，总 $O(M+L)$ 。
空间复杂度： $O(M+L)$ 。

E - Yacht

题目链接：https://atcoder.jp/contests/abc421/tasks/abc421_e

题目大意

有 5 枚六面骰子，每枚骰子六个面分别写着 $A_1,\dots,A_6$ （允许有相同的数），每个面向上的概率均为 $1/6$ 。游戏流程：

掷全部 5 枚骰子并观察结果，可任意保留若干枚（可为 0）；
重掷未被保留的骰子，观察结果，可再从新结果中任意保留若干枚（之前保留的始终保留）；
重掷仍未保留的骰子并观察结果；
任选一个数 $X$ ，设 5 枚骰子中显示 $X$ 的有 $n$ 枚，得分 $nX$ 。

求在最优策略下的期望得分。要求误差 $\le 10^{-5}$ 。

思路

这是一个"每次掷完后决定保留哪些骰子"的决策问题，用带记忆化的概率 DP 求解。

设 $f(k,S)$ 表示：还剩 $k$ 次掷骰机会，当前保留的骰子的值构成多重集 $S$ 时，最优的期望得分。设 $r=5-|S|$ 为本轮要掷的骰子数。掷 $r$ 枚骰子得到结果多重集 $P$ 的概率为 $\mathrm{Prob}(P)$ （多项式分布，见下）。分两类：

$k=1$ （最后一次掷骰）：掷完后游戏结束，直接选最优的 $X$ ，得分为 $\mathrm{Score}(S\cup P)=\max_{v}\bigl(\text{count}_v(S\cup P)\cdot v\bigr),$ 因此 $f(1,S)=\sum_P \mathrm{Prob}(P)\cdot \mathrm{Score}(S\cup P).$
$k>1$ ：掷出 $P$ 后，可以选择再保留 $P$ 的任意子多重集 $T\subseteq P$ （其余继续重掷），应取最优者： $f(k,S)=\sum_P \mathrm{Prob}(P)\cdot \max_{T\subseteq P} f(k-1,\ S\cup T).$

答案即为 $f(3,\varnothing)$ 。

为什么状态很少：保留的骰子数不超过 5，每枚取值至多 6 种，因此保留多重集 $S$ 的种类数为 $\binom{6+5}{5}=462$ 量级；对每个状态，结果多重集 $P$ 的种类数至多 $\binom{r+5}{5}\le 252$ ，子多重集 $T$ 至多 $2^r\le 32$ 种。按官方题解的分析，记忆化递归的总调用次数不超过 $2\sum_S 12^{5-|S|}\le 10^6$ ，完全可行。

实现要点：

把 $A$ 中相同的值合并：不同的值记为 $v_0,\dots,v_{D-1}$ ，掷一次得到 $v_j$ 的概率为 $p_j=\dfrac{\text{freq}(v_j)}{6}$ 。
掷 $r$ 枚骰子得到计数为 $(c_0,\dots,c_{D-1})$ 的结果的概率为多重分布 $\mathrm{Prob}(P)=\frac{r!}{c_0!\cdots c_{D-1}!}\prod_j p_j^{c_j}.$ 可用递推方式逐个确定每种值的个数并累乘组合数，避免大数运算。
状态用计数向量 $S=(s_0,\dots,s_{D-1})$ （ $\sum s_j\le 5$ ）编码，按 $k$ 分别记忆化。
$\mathrm{Score}$ 直接对计数取 $\max_j (s_j\cdot v_j)$ 即可。

参考代码

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

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

    vector<int> A(6);
    for (int i = 0; i < 6; i++) cin >> A[i];

    // 不同的值及其出现概率
    vector<int> vals;
    for (int i = 0; i < 6; i++) {
        bool dup = false;
        for (int v : vals) if (v == A[i]) dup = true;
        if (!dup) vals.push_back(A[i]);
    }
    int D = (int)vals.size();
    vector<double> p(D, 0.0);
    for (int i = 0; i < 6; i++)
        for (int j = 0; j < D; j++)
            if (A[i] == vals[j]) p[j] += 1.0 / 6.0;

    map<vector<int>, double> memo[4];   // memo[k][S]

    function<double(int, vector<int>)> f = [&](int k, vector<int> S) -> double {
        auto it = memo[k].find(S);
        if (it != memo[k].end()) return it->second;

        int r = 5;
        for (int c : S) r -= c;

        double res = 0.0;
        vector<int> P(D, 0);            // 本轮掷骰结果（计数）

        // 枚举 r 枚骰子的所有结果多重集 P
        function<void(int, int, double)> gen = [&](int j, int remain, double prob) {
            if (j == D) {
                if (remain != 0) return;
                if (k == 1) {
                    double sc = 0.0;
                    for (int t = 0; t < D; t++)
                        sc = max(sc, (double)(S[t] + P[t]) * vals[t]);
                    res += prob * sc;
                } else {
                    double best = -1e18;
                    vector<int> T(D, 0);   // 本轮额外保留的子多重集
                    function<void(int)> genT = [&](int jj) {
                        if (jj == D) {
                            vector<int> U = S;
                            for (int t = 0; t < D; t++) U[t] += T[t];
                            best = max(best, f(k - 1, U));
                            return;
                        }
                        for (int t = 0; t <= P[jj]; t++) {
                            T[jj] = t;
                            genT(jj + 1);
                        }
                    };
                    genT(0);
                    res += prob * best;
                }
                return;
            }
            double comb = 1.0;            // C(remain, c)
            for (int c = 0; c <= remain; c++) {
                P[j] = c;
                double pw = 1.0;
                for (int t = 0; t < c; t++) pw *= p[j];
                gen(j + 1, remain - c, prob * comb * pw);
                comb = comb * (remain - c) / (c + 1);
            }
        };

        gen(0, r, 1.0);
        memo[k][S] = res;
        return res;
    };

    vector<int> empty(D, 0);
    double ans = f(3, empty);
    cout << fixed << setprecision(10) << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度：状态数 $\le \binom{11}{5}=462$ ，每个状态枚举 $\le 252$ 种结果 $\times$ $\le 32$ 种子集，总枚举量 $\le 10^6$ ，可视为常数。
空间复杂度： $O(\text{状态数})$ 。

F - Erase between X and Y

题目链接：https://atcoder.jp/contests/abc421/tasks/abc421_f

题目大意

初始序列 $A=(0)$ 。按顺序处理 $Q$ 个询问， $Q\le 5\times 10^5$ ：

1 x：把当前询问的编号 $i$ 插到值 $x$ 在 $A$ 中出现的位置之后；
2 x y：删除 $A$ 中 $x$ 与 $y$ 之间的所有元素（不含 $x,y$ 本身），输出被删元素之和，并把 $A$ 更新为（…, x, y, …）。

保证操作前 $x,y$ 都在 $A$ 中，且处理过程中 $A$ 中每个值至多出现一次（因此位置唯一）。

思路

因为值互不相同，可以用链表维护序列：记 $\text{nxt}[v]$ 为值 $v$ 在 $A$ 中后一个位置的值，若 $v$ 在末尾则为 $-1$ 。初始只有值 $0$ ， $\text{nxt}[0]=-1$ 。

类型 1（插入）：要把 $i$ 插到 $x$ 之后。若插入前 $\text{nxt}[x]=y$ ，则链 … $\to x\to y\to\dots$ 变为 … $\to x\to i\to y\to\dots$ ，只需更新

\text{nxt}[i]=\text{nxt}[x],\qquad \text{nxt}[x]=i,

其余元素不受影响， $O(1)$ 完成。

类型 2（删除）：需要找出 $x,y$ 谁在前，累加两者之间所有值并输出，然后把它们"缝合"起来。直接判断谁在前需要额外信息，这里采用双指针交替推进：两个指针分别从 $x$ 与 $y$ 出发沿 $\text{nxt}$ 前进，同时累加途经值（分别为 $sx,sy$ ）：

若从 $x$ 出发的指针先到达 $y$ ，说明 $x$ 在 $y$ 之前，输出 $sx$ ，并令 $\text{nxt}[x]=y$ ；
若从 $y$ 出发的指针先到达 $x$ ，说明 $y$ 在 $x$ 之前，输出 $sy$ ，并令 $\text{nxt}[y]=x$ 。

虽然单次删除可能遍历若干节点，但每个被删的元素只会被遍历常数次，而插入总共只有 $Q$ 次、最多产生 $Q$ 个元素，因此所有删除遍历的总和为 $O(Q)$ ，整体摊还 $O(Q)$ 。

细节：

被插入的值就是查询编号 $i$ ，范围 $1\dots Q$ ，加上初始的 $0$ ，所以 nxt 数组开 $Q+1$ 即可；
类型 2 中被删元素之和可能很大：最多 $Q$ 个数、每个最大 $Q$ ，和可达约 $1.25\times 10^{11}$ ，必须用 long long；
若 $x,y$ 相邻（之间无元素），遍历一步即相遇，输出 $0$ ，此时 $\text{nxt}[x]=y$ 是"原地缝合"，正确。

参考代码

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

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

    int Q;
    cin >> Q;
    vector<int> nxt(Q + 1, -1);   // nxt[v] : 值 v 在 A 中后面相邻的值，末尾为 -1
    nxt[0] = -1;

    for (int i = 1; i <= Q; i++) {
        int t;
        cin >> t;
        if (t == 1) {
            int x;
            cin >> x;
            nxt[i] = nxt[x];
            nxt[x] = i;
        } else {
            int x, y;
            cin >> x >> y;
            int cx = x, cy = y;
            long long sx = 0, sy = 0;
            while (true) {
                if (nxt[cx] != -1) {
                    cx = nxt[cx];
                    if (cx == y) {            // x 在前，x 与 y 之间的元素已被累加到 sx
                        cout << sx << '\n';
                        nxt[x] = y;
                        break;
                    } else {
                        sx += cx;
                    }
                }
                if (nxt[cy] != -1) {
                    cy = nxt[cy];
                    if (cy == x) {            // y 在前
                        cout << sy << '\n';
                        nxt[y] = x;
                        break;
                    } else {
                        sy += cy;
                    }
                }
            }
        }
    }
    return 0;
}

复杂度分析

时间复杂度：插入 $O(1)$ ；删除的遍历总代价与被删元素总数同阶，摊还 $O(Q)$ 。
空间复杂度： $O(Q)$ 。

G - Increase to make it Increasing

题目链接：https://atcoder.jp/contests/abc421/tasks/abc421_g

题目大意

给定长度 $N$ 的整数序列 $A$ （ $A_i\ge 1$ ）和 $M$ 个区间 $(L_i,R_i)$ 。一次操作可任选一个 $i$ ，把 $A_{L_i},A_{L_i+1},\dots,A_{R_i}$ 全部加 $1$ 。判断能否通过若干次操作使 $A$ 单调不减，若能则求最少操作次数，否则输出 $-1$ 。 $N,M\le 300$ ， $A_i\le 300$ 。

思路

差分转化。定义差分数组 $d=(d_0,d_1,\dots,d_N)$ ：

d_0=A_1,\qquad d_i=A_{i+1}-A_i\ (1\le i\le N-1),\qquad d_N=-A_N.

一次对区间 $[L,R]$ 的操作，等价于 $d_{L-1}$ 加 $1$ 、 $d_R$ 减 $1$ 。而 $A$ 单调不减等价于 $A_{i+1}\ge A_i$ （ $1\le i\le N-1$ ）且 $A_1\ge 0$ （恒真），即

d_0,d_1,\dots,d_{N-1}\ge 0,\qquad d_N\text{ 可任意}.

球的模型。把差分值想象成 $N+1$ 个盒子 $0,1,\dots,N$ 里的球：

$d_j>0$ （ $0\le j\le N-1$ ）表示盒子 $j$ 有 $d_j$ 个多余的球；
$d_j<0$ （ $0\le j\le N-1$ ）表示盒子 $j$ 还需要 $-d_j$ 个球；
盒子 $N$ 有无限多的多余球（因为 $d_N$ 允许任意负）。

一次区间操作 $[L,R]$ 等价于把 $1$ 个球从盒子 $R$ 移到盒子 $L-1$ （ $d_{L-1}$ 增加、 $d_R$ 减少）。目标是用最少的移动次数把多余球送到所有需要球的位置。这正是一个最小费用流问题。

建图。构造图 $G$ ，顶点为盒子 $0..N$ 再加源点 $S$ 、汇点 $T$ ：

对每个 $d_j>0$ （ $0\le j\le N-1$ ）： $S\to j$ ，容量 $d_j$ ，费用 $0$ ；
对每个 $d_j<0$ （ $0\le j\le N-1$ ）： $j\to T$ ，容量 $-d_j$ ，费用 $0$ ；
$S\to N$ ，容量 $+\infty$ ，费用 $0$ （盒子 $N$ 的无限供给）；
对每个操作 $i$ ： $R_i\to L_i-1$ ，容量 $+\infty$ ，费用 $1$ （搬 1 个球花 1 次操作）。

记需求总量 $K=\sum_{0\le j\le N-1}\max(-d_j,0)$ 。求 $S$ 到 $T$ 的最小费用最大流：若最大流 $<K$ ，说明有些需求无法被满足，输出 $-1$ ；否则答案为最小费用最大流的费用。

正确性：从 $S$ 出发的一条流代表"一个多余球经过一系列搬运（每条边是一次区间操作）到达某个需求位置"，路径经过的边数即花费的操作次数；最小费用最大流即满足所有需求所需的最少操作总数。反过来，任何一组可行操作方案都对应图上的一个可行流，因此最小费用流给出的正是最优值。费用非负，可用 Dijkstra 实现的最短路增广（successive shortest path）求解。

复杂度：最大流值 $K\le \sum |d_j|\le N\cdot \max A_i\le 9\times 10^4$ ，每次增广为一次 Dijkstra， $O((N+M)\log(N+M))$ ，总复杂度 $O\bigl(N\cdot\max A_i\cdot(N+M)\log(N+M)\bigr)$ 。官方题解使用了 atcoder 库的 mcf_graph，下面给出不依赖外部库的自实现版本（思路完全相同）。

参考代码

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

using ll = long long;
const ll INF = (1LL << 60);

// 最小费用流：所有费用非负，用 Dijkstra + 势能 (primal-dual) 实现
struct MinCostFlow {
    struct Edge {
        int to, rev;
        ll cap, cost;
    };
    int n;
    vector<vector<Edge>> g;
    MinCostFlow(int n) : n(n), g(n) {}

    void add_edge(int from, int to, ll cap, ll cost) {
        g[from].push_back({to, (int)g[to].size(), cap, cost});
        g[to].push_back({from, (int)g[from].size() - 1, 0, -cost});
    }

    // 返回 (最大流, 最小费用)，maxf 为流量上限
    pair<ll, ll> min_cost_flow(int s, int t, ll maxf = INF) {
        ll flow = 0, cost = 0;
        vector<ll> h(n, 0), dist(n);
        vector<int> prevv(n), preve(n);
        while (flow < maxf) {
            priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
            fill(dist.begin(), dist.end(), INF);
            dist[s] = 0;
            pq.push({0, s});
            while (!pq.empty()) {
                auto [d, v] = pq.top();
                pq.pop();
                if (dist[v] < d) continue;
                for (int i = 0; i < (int)g[v].size(); i++) {
                    Edge &e = g[v][i];
                    if (e.cap <= 0) continue;
                    ll nd = dist[v] + e.cost + h[v] - h[e.to];
                    if (nd < dist[e.to]) {
                        dist[e.to] = nd;
                        prevv[e.to] = v;
                        preve[e.to] = i;
                        pq.push({nd, e.to});
                    }
                }
            }
            if (dist[t] == INF) break;
            for (int v = 0; v < n; v++)
                if (dist[v] < INF) h[v] += dist[v];
            ll d = maxf - flow;
            for (int v = t; v != s; v = prevv[v])
                d = min(d, g[prevv[v]][preve[v]].cap);
            flow += d;
            cost += d * h[t];
            for (int v = t; v != s; v = prevv[v]) {
                Edge &e = g[prevv[v]][preve[v]];
                e.cap -= d;
                g[v][e.rev].cap += d;
            }
        }
        return {flow, cost};
    }
};

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

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

    MinCostFlow mcf(N + 3);
    int S = N + 1, T = N + 2;

    ll K = 0;   // 总需求
    for (int i = 0; i < N; i++) {
        int d = A[i] - (i ? A[i - 1] : 0);   // d_0 = A_1, d_i = A_{i+1} - A_i
        if (d > 0) mcf.add_edge(S, i, d, 0);
        else if (d < 0) {
            mcf.add_edge(i, T, -d, 0);
            K += -d;
        }
    }
    mcf.add_edge(S, N, INF, 0);   // 盒子 N 有无限多余的球

    for (int i = 0; i < M; i++) {
        int L, R;
        cin >> L >> R;
        --L;                        // L_i - 1（下标转 0-based）
        mcf.add_edge(R, L, INF, 1); // 从盒子 R 搬 1 个球到盒子 L-1，花费 1 次操作
    }

    auto [flow, cost] = mcf.min_cost_flow(S, T);
    if (flow < K) cout << -1 << '\n';
    else cout << cost << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O\bigl(K\cdot(N+M)\log(N+M)\bigr)$ ，其中 $K\le N\cdot\max A_i\le 9\times 10^4$ ，即 $O\bigl(N\cdot\max A_i\cdot(N+M)\log(N+M)\bigr)$ 。
空间复杂度： $O(N+M)$ 。