AtCoder Beginner Contest 427 题解

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

AtCoder Beginner Contest 427 题解

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

比赛概览

本场整体难度中等偏易：A、B 是入门题，C、D 是简单的暴力/DP 题，E、F、G 三题（BFS 状态压缩、折半搜索、带变换的数据结构维护）是主要的区分点，其中 G 最有深度。A、B 考察基础字符串处理与模拟；C 的关键是把"删边使图二分"转化为"枚举 $2^N$ 种黑白染色、统计同色边数取最小"；D 是博弈论中经典的"从终局倒推"DP，需注意 Bob 回合是"与"语义；E 需要观察"垃圾整体平移"的结构，用六参数状态做 BFS；F 是 meet-in-the-middle 与斐波那契计数，重点是把"不选相邻元素"的约束压缩到可枚举规模；G 需要把任意礼物序列化简为"好序列"并设计支持区间打标记的平衡树来维护，是全场最值得反复琢磨的一题。

A - ABC -> AC

题目链接：https://atcoder.jp/contests/abc427/tasks/abc427_a

题目大意

给定一个长度为奇数 $L$ （ $3\le L\le 9$ ）的大写字母字符串 $S$ ，删除它的中间字符（即第 $\frac{L+1}{2}$ 个字符），输出结果字符串。

思路

这是最基础的字符串操作题。唯一需要注意的是"中间字符"的定位： $L$ 为奇数时，1-based 的中间位置是 $\frac{L+1}{2}$ ，换算成 0-based 下标就是 $\frac{L+1}{2}-1=\frac{L-1}{2}$ 。由于 $L$ 是奇数， $\frac{L-1}{2}=\lfloor L/2\rfloor=L/2$ （整数除法），所以 L / 2 恰好是中间字符的 0-based 下标。

用 std::string 的 erase 接口删除该字符即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    s.erase(s.begin() + (int)s.size() / 2);
    cout << s << '\n';
}

复杂度分析

时间复杂度： $O(L)$
空间复杂度： $O(L)$

B - Sum of Digits Sequence

题目链接：https://atcoder.jp/contests/abc427/tasks/abc427_b

题目大意

定义 $f(x)$ 为 $x$ 的十进制数位和。给定递推数列： $A_0=1$ ，且对 $i\ge 1$ ， $A_i=\sum_{j=0}^{i-1}f(A_j)$ 。输入正整数 $N$ （ $1\le N\le 100$ ），求 $A_N$ 。

思路

按题意直接模拟即可。数位和函数 $f(x)$ 可以用"反复取模除以 10"实现，也可以用字符串转换实现。

由于 $N\le 100$ ，直接按定义二重循环计算 $A_i=\sum_{j<i}f(A_j)$ 已经足够。

另外可以观察到一个小优化：记 $S_i=\sum_{j=0}^{i-1}f(A_j)$ ，那么 $A_i=S_i$ ，于是

S_{i+1}=S_i+f(A_i)=S_i+f(S_i).

即从 $S_1=f(A_0)=f(1)=1$ 出发，每次令 $S_{i+1}=S_i+f(S_i)$ ，最后 $A_N=S_N$ 。两种写法本质上相同，这里给出直观的二重循环版本。

数值范围注意点：虽然 $A_i$ 会增长，但每一步只是在累加若干个数位和，数位和的量级很小（约 $9\times$ 位数），所以 $A_{100}$ 至多几千，int 足够；代码中使用 long long 则完全安全。

参考代码

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

int f(int x) {
    int res = 0;
    while (x) {
        res += x % 10;
        x /= 10;
    }
    return res;
}

int main() {
    int n;
    cin >> n;
    vector<long long> a(n + 1);
    a[0] = 1;
    for (int i = 1; i <= n; i++) {
        long long s = 0;
        for (int j = 0; j < i; j++) s += f(a[j]);
        a[i] = s;
    }
    cout << a[n] << '\n';
}

复杂度分析

时间复杂度： $O(N^2)$ （单次数位和为 $O(\log A_i)$ ，可视作常数）
空间复杂度： $O(N)$

C - Bipartize

题目链接：https://atcoder.jp/contests/abc427/tasks/abc427_c

题目大意

给定一个 $N$ 个点 $M$ 条边的简单无向图。每次操作可以删除一条尚未删除的边。问最少需要删几条边，才能使剩余的图成为二分图。

思路

关键转化：二分图等价于存在一种把每个顶点染成黑白两色、且每条边两个端点异色的染色方案。反过来，如果先固定一种染色方案，那么"为了让每条边端点异色至少要删多少条边"就等于该染色方案下同色边的条数——两端异色的边已经满足要求，两端同色的边必须删掉。

于是枚举 $2^N$ 种染色方案，对每种方案统计同色边数 $c$ ，答案就是所有方案中 $c$ 的最小值 $m$ 。

为什么 $m$ 等于原问题答案：

对任意染色方案，删掉全部同色边后，剩余图满足"每条边端点异色"，故是二分图。所以 $m\ge$ 原问题答案（ $m$ 给出了一种可行方案，即上界）；
反过来，设最优删边方案（删 $k$ 条边）得到的二分图存在一个染色使每条边端点异色。在这个染色下，同色边数恰好等于被删的 $k$ 条边，因此 $m\le k$ 。即 $m$ 也是原问题答案的下界。

综上， $m$ 等于答案。

$N\le 10$ ， $2^N\le 1024$ ， $M\le 45$ ，枚举完全可行。实现时用整数 bit 的二进制位表示染色：第 $j$ 位为 1 表示顶点 $j$ 为黑（0 为白）。对每条边 $(u,v)$ ，比较 (bit >> u) & 1 与 (bit >> v) & 1 是否相等即可判断是否同色。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int N, M;
    cin >> N >> M;
    vector<pair<int, int>> edges(M);
    for (auto& [u, v] : edges) {
        cin >> u >> v;
        --u; --v;
    }
    int ans = M;
    for (int bit = 0; bit < (1 << N); ++bit) {
        int del = 0;
        for (auto& [u, v] : edges) {
            if (((bit >> u) & 1) == ((bit >> v) & 1)) ++del;
        }
        ans = min(ans, del);
    }
    cout << ans << '\n';
}

官方题解也给出了 Python 版本：

N, M = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(M)]

ans = M
for bit in range(2 ** N):
    del_cnt = 0
    for u, v in edges:
        if (1 & (bit >> u)) == (1 & (bit >> v)):
            del_cnt += 1
    ans = min(ans, del_cnt)

print(ans)

复杂度分析

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

D - The Simple Game

题目链接：https://atcoder.jp/contests/abc427/tasks/abc427_d

题目大意

给定一个 $N$ 点 $M$ 边的有向图（每个点出度至少为 1），每个点上写有字符 A 或 B。棋子初始在点 1。Alice 先手、Bob 后手，轮流沿有向边把棋子移动一格，每人各走 $K$ 步（总共 $2K$ 步）。若最终停在写有 A 的点上 Alice 胜，停在 B 上 Bob 胜。双方都最优时，判断胜者。有 $T$ 组数据。

思路

经典的"从终局倒推"博弈 DP。设 $dp_{i,j}$ 表示已经走了 $i$ 步、棋子当前在点 $j$ 时，Alice 是否必胜（布尔值），其中 $i=0,1,\dots,2K$ 。

终局 $i=2K$ ：直接看点上字符， $dp_{2K,j}=[S_j=\texttt{A}]$ 。
轮到 Alice 走（ $i$ 为偶数）：Alice 可以选择任意一步，只要存在一步能走到"Alice 必胜"的状态，她就必胜：

dp_{i,j}=\bigvee_{(j,v)\in E}dp_{i+1,v}.

轮到 Bob 走（ $i$ 为奇数）：Bob 会尽量让 Alice 输。Alice 必胜当且仅当 Bob 无论怎么走，所有后继状态 Alice 都必胜：

dp_{i,j}=\bigwedge_{(j,v)\in E}dp_{i+1,v}.

由于每个点出度至少为 1，上面的"与/或"不会被空集干扰（不会出现没有后继的情况）。答案就是 $dp_{0,1}$ ：为真输出 Alice，否则输出 Bob。

易错点：Bob 回合是"与"而不是"或"。直觉记忆：谁当前走，谁就选择对自己有利的方向——Alice 选"存在一条路通向胜利"，Bob 选"让所有路都对 Alice 不利"。官方题解中 Bob 回合的文字表述容易引起歧义（其含义是：若 Bob 能找到一步使 $dp_{i+1,v}$ 为假，则 Alice 并不必胜），务必以"与"逻辑为准。例如样例 2 中若把 Bob 回合误写成"或"，会得到错误的 Alice。

复杂度：状态数 $O(NK)$ ，转移总复杂度 $O((N+M)K)$ 。由于 $\sum N,\sum M\le 2\times 10^5$ 且 $K\le 10$ ，完全可行。

参考代码

#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, M, K;
        cin >> N >> M >> K;
        string S;
        cin >> S;
        vector<vector<int>> adj(N);
        for (int i = 0; i < M; i++) {
            int u, v;
            cin >> u >> v;
            --u; --v;
            adj[u].push_back(v);
        }
        int steps = 2 * K;
        vector<vector<char>> dp(steps + 1, vector<char>(N));
        for (int j = 0; j < N; j++) dp[steps][j] = (S[j] == 'A');
        for (int i = steps - 1; i >= 0; i--) {
            if (i % 2 == 0) {          // Alice's turn: exists a winning move
                for (int j = 0; j < N; j++) {
                    bool res = false;
                    for (int v : adj[j]) res = res || dp[i + 1][v];
                    dp[i][j] = res;
                }
            } else {                    // Bob's turn: every move must lead to Alice's win
                for (int j = 0; j < N; j++) {
                    bool res = true;
                    for (int v : adj[j]) res = res && dp[i + 1][v];
                    dp[i][j] = res;
                }
            }
        }
        cout << (dp[0][0] ? "Alice" : "Bob") << '\n';
    }
}

复杂度分析

时间复杂度： $O((N+M)K)$ 每组数据，总体 $O\left(\sum(N+M)\cdot K\right)$
空间复杂度： $O(NK)$

E - Wind Cleaning

题目链接：https://atcoder.jp/contests/abc427/tasks/abc427_e

题目大意

$H\times W$ 的网格，Takahashi 站在一格（标记为 T）上，某些格放有垃圾（#）。每次操作可以选择上、下、左、右之一，把所有垃圾同时向该方向平移一格；移出网格的垃圾消失，若有垃圾平移到 Takahashi 所在的格子则他会变脏。问能否在不弄脏的前提下让所有垃圾消失，若能输出最少操作次数，否则输出 -1。

思路

Takahashi 从不移动，而垃圾又总是整体平移，所以当前垃圾集合完全决定了局面。这让我们可以把"垃圾摆放状态"看作图的顶点，两个状态之间连一条边当且仅当能通过一步操作互相到达，答案就是初始状态到"没有垃圾"状态的最短路。直接枚举垃圾集合不可行（最多 $2^{HW}$ 种），关键在于压缩状态。

核心观察：任意时刻的垃圾集合一定可以写成以下形式：

初始时位于矩形 $[lx,rx)\times[ly,ry)$ 内的垃圾，整体平移 $(dx,dy)$ 后的结果；此外没有其他垃圾。

理由是垃圾始终一起移动：向某个方向平移只会把最前沿的一行（或一列）推出界外，因此被剪掉的部分永远是初始坐标的一个前缀（行方向）和一个前缀（列方向）。于是状态用六元组 $(lx,rx,ly,ry,dx,dy)$ 表示即可，各参数范围为

0\le lx,rx\le H,\quad 0\le ly,ry\le W,\quad -H\le dx\le H,\quad -W\le dy\le W,

状态总数 $O(H^3W^3)$ 。 $H,W\le 12$ 时约为 $10^6\sim 10^7$ 量级，BFS 可行。

状态的转移规则（这里 $dx,dy$ 表示"初始坐标 → 当前坐标"的偏移；垃圾落在网格内需要 $lx+dx\ge 0$ 、 $rx-1+dx<H$ ，列同理）：

向上移： $dx'\gets dx-1$ ，并把超出上界的行剪掉， $lx'\gets\max(lx,\,-dx')$ ； $rx$ 不变。
向下移： $dx'\gets dx+1$ ， $rx'\gets\min(rx,\,H-dx')$ ； $lx$ 不变。
向左移： $dy'\gets dy-1$ ， $ly'\gets\max(ly,\,-dy')$ 。
向右移： $dy'\gets dy+1$ ， $ry'\gets\min(ry,\,W-dy')$ 。

BFS 每次扩展时：

按上述规则算出新状态；
判断是否会被弄脏：若新状态下有垃圾落在 Takahashi 的格子 $(r_T,c_T)$ ，即存在初始垃圾 $(x,y)$ 满足 $x\in[lx',rx'),\ y\in[ly',ry')$ 且 $x+dx'=r_T,\ y+dy'=c_T$ ，则这一操作会弄脏他，跳过；
判断是否达成目标：用初始垃圾的二维前缀和判断矩形 $[lx',rx')\times[ly',ry')$ 内是否有初始垃圾，若没有则到达目标状态。

为什么正确：BFS 在"操作序列 → 状态"的图上求最短路；每个六元组状态精确刻画了当前的垃圾集合，而目标判定只看实际垃圾是否存在，因此 BFS 求出的距离就是最小操作数。若 BFS 结束后仍未到达目标，则输出 $-1$ 。

实现要点：把六元组编码成一个 32 位整数作为哈希键，注意编码与解码必须严格互逆（各分量按各自取值范围取模、进位）。

参考代码

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

int H, W;
int TR, TC;   // Takahashi's cell

// State: trash = initial trash inside rows [lx,rx) and cols [ly,ry), shifted by (dx,dy).
int encode(int lx, int rx, int ly, int ry, int dx, int dy) {
    int dxx = dx + H, dyy = dy + W;
    int k = lx;
    k = k * (H + 1) + rx;
    k = k * (W + 1) + ly;
    k = k * (W + 1) + ry;
    k = k * (2 * H + 1) + dxx;
    k = k * (2 * W + 1) + dyy;
    return k;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> H >> W;
    vector<string> S(H);
    for (int i = 0; i < H; i++) cin >> S[i];

    // 2D prefix sum of the initial trash
    vector<vector<int>> pre(H + 1, vector<int>(W + 1, 0));
    for (int i = 0; i < H; i++)
        for (int j = 0; j < W; j++) {
            if (S[i][j] == 'T') { TR = i; TC = j; }
            pre[i + 1][j + 1] = pre[i + 1][j] + pre[i][j + 1] - pre[i][j]
                                + (S[i][j] == '#');
        }
    auto trashCount = [&](int x1, int x2, int y1, int y2) {
        x1 = max(x1, 0); x2 = min(x2, H);
        y1 = max(y1, 0); y2 = min(y2, W);
        if (x1 >= x2 || y1 >= y2) return 0;
        return pre[x2][y2] - pre[x1][y2] - pre[x2][y1] + pre[x1][y1];
    };
    auto hasTrashOnT = [&](int lx, int rx, int ly, int ry, int dx, int dy) {
        int x = TR - dx, y = TC - dy;   // original coords whose image is T's cell
        if (x < lx || x >= rx || y < ly || y >= ry) return false;
        return S[x][y] == '#';
    };

    auto decode = [&](int key, int& lx, int& rx, int& ly, int& ry, int& dx, int& dy) {
        int dyy = key % (2 * W + 1); key /= (2 * W + 1);
        int dxx = key % (2 * H + 1); key /= (2 * H + 1);
        ry = key % (W + 1); key /= (W + 1);
        ly = key % (W + 1); key /= (W + 1);
        rx = key % (H + 1); key /= (H + 1);
        lx = key;
        dx = dxx - H; dy = dyy - W;
    };

    int start = encode(0, H, 0, W, 0, 0);
    unordered_map<int, int> dist;
    dist.reserve(1 << 20);
    dist[start] = 0;
    queue<int> q;
    q.push(start);

    const int dR[4] = {-1, 1, 0, 0};
    const int dC[4] = {0, 0, -1, 1};
    int ans = -1;
    while (!q.empty()) {
        int key = q.front(); q.pop();
        int lx, rx, ly, ry, dx, dy;
        decode(key, lx, rx, ly, ry, dx, dy);
        if (trashCount(lx, rx, ly, ry) == 0) { ans = dist[key]; break; }
        int nd = dist[key] + 1;
        for (int k = 0; k < 4; k++) {
            int ndx = dx + dR[k], ndy = dy + dC[k];
            int nlx = max(lx, -ndx);            // clip rows that would fall off
            int nrx = min(rx, H - ndx);
            int nly = max(ly, -ndy);
            int nry = min(ry, W - ndy);
            if (hasTrashOnT(nlx, nrx, nly, nry, ndx, ndy)) continue;  // would get dirty
            int nk = encode(nlx, nrx, nly, nry, ndx, ndy);
            if (!dist.count(nk)) { dist[nk] = nd; q.push(nk); }
        }
    }
    cout << ans << '\n';
}

复杂度分析

时间复杂度： $O(H^3W^3)$ （BFS 状态数上界；每状态 4 个转移，目标判定与"是否弄脏"判定均为 $O(1)$ ）
空间复杂度： $O(H^3W^3)$

F - Not Adjacent

题目链接：https://atcoder.jp/contests/abc427/tasks/abc427_f

题目大意

给定长度为 $N$ 的整数序列 $A$ 。求有多少个子序列（按下标严格递增选取；即使两个子序列作为整数序列相同，只要取的位置不同就算不同）满足：没有选取在原序列中相邻的两个元素，且所选元素之和是 $M$ 的倍数。空子序列也计入（其和为 0）。

思路

$N\le 60$ ，枚举 $2^N$ 种选取不可能。但"不选相邻元素"这一限制极大地压缩了子序列数量：长度为 $n$ 的序列中不选相邻元素的子序列个数为斐波那契数 $\operatorname{fib}_n$ ，其中

\operatorname{fib}_0=1,\quad \operatorname{fib}_1=2,\quad \operatorname{fib}_{i+2}=\operatorname{fib}_{i+1}+\operatorname{fib}_i.

$N=60$ 时 $\operatorname{fib}_{30}=2178309$ ，约 $2.2\times 10^6$ ，这正是 meet-in-the-middle 的切入点。

算法：

把 $A$ 分成前 $\lfloor N/2\rfloor$ 个元素的左半和 $\lceil N/2\rceil$ 个元素的右半。
分别枚举两半所有"不选相邻元素"的子序列，记录其和模 $M$ 的结果。特别地，对左半还要区分"是否选了左半最后一个元素 $A_{m-1}$ "；对右半（反转后枚举）要区分"是否选了右半第一个元素 $A_m$ "。因为两半拼接成完整子序列时，唯一的跨边界相邻约束就是 $A_{m-1}$ 与 $A_m$ 不能同时被选。
答案 = 所有（左半子序列, 右半子序列）的和模 $M$ 为 0 的对数 − 同时选了 $A_{m-1}$ 与 $A_m$ 的非法对数。

如何枚举（斐波那契 DP）：设 used 为"包含当前已处理部分的最后一个元素"的不相邻子序列和集合，unused 为"不包含最后一个元素"的集合。每加入一个新元素 $x$ ：

新的 used = 旧的 unused 中每个和加上 $x$ （因为新选的 $x$ 必然与旧部分最后一个元素相邻，所以只能接在"不含旧最后一个元素"的子序列后面）；
新的 unused = 旧的 used 与旧的 unused 的并（不选 $x$ ，旧子序列照搬）。

每处理一个元素，集合规模恰好按斐波那契增长。官方题解用 swap 技巧在 used 上原地完成上述两种变换，非常简洁。

计数：对左半的每个和 $a$ ，需要在右半中统计 $b=(M-a)\bmod M$ 的出现次数。由于右半的 all 已排序，用 lower_bound/upper_bound 二分即可。对"非法对数"，用左半的 used 与右半的 used 各做一次同样的统计再减去。

边界情况： $N=1$ 时左半为空，solve 对空序列返回 used={}、all={0}，程序无需特判也能正确处理。

参考代码

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

// used: sums (mod M) of non-adjacent subsequences including the last element;
// all : sums of all non-adjacent subsequences. Both sorted ascending.
pair<vector<ll>, vector<ll>> solve(const vector<ll>& seq, ll M) {
    vector<ll> used, unused;
    unused.push_back(0);
    for (ll x : seq) {
        swap(used, unused);
        for (auto& v : used) {
            unused.push_back(v);
            v = (v + x) % M;
        }
    }
    vector<ll> all = used;
    all.insert(all.end(), unused.begin(), unused.end());
    sort(all.begin(), all.end());
    sort(used.begin(), used.end());
    return {used, all};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll N, M;
    cin >> N >> M;
    vector<ll> A(N);
    for (auto& a : A) cin >> a;

    int m = (int)(N / 2);
    vector<ll> leftA(A.begin(), A.begin() + m);
    vector<ll> rightA(A.begin() + m, A.end());
    reverse(rightA.begin(), rightA.end());   // so "used" = picks the first element of the right half

    auto [left_used, left_all] = solve(leftA, M);
    auto [right_used, right_all] = solve(rightA, M);

    ll ans = 0;
    for (ll a : left_all) {
        ll target = (M - a) % M;
        ans += (ll)(upper_bound(right_all.begin(), right_all.end(), target) -
                    lower_bound(right_all.begin(), right_all.end(), target));
    }
    for (ll a : left_used) {
        ll target = (M - a) % M;
        ans -= (ll)(upper_bound(right_used.begin(), right_used.end(), target) -
                    lower_bound(right_used.begin(), right_used.end(), target));
    }
    cout << ans << '\n';
}

复杂度分析

时间复杂度： $O(\operatorname{fib}_{\lfloor N/2\rfloor}\log\operatorname{fib}_{\lceil N/2\rceil})=O\left(N\left(\frac{1+\sqrt5}{2}\right)^N\right)$
空间复杂度： $O(\operatorname{fib}_{\lceil N/2\rceil})$

G - Takahashi's Expectation 2

题目链接：https://atcoder.jp/contests/abc427/tasks/abc427_g

题目大意

Takahashi 有一个整数参数"心情值"，每收到一件礼物心情都会改变：若礼物价值 $P$ 大于等于当前心情，他开心，心情增加 $A$ ；若 $P$ 小于当前心情，他失望，心情减少 $B$ 。初始有 $N$ 件将要依次收到的礼物（价值 $P_i$ 已知），之后有 $Q$ 个操作：1 X 表示在队尾追加一件价值 $X$ 的礼物；2 X 表示询问"若初始心情为 $X$ ，收完当前全部礼物后最终心情是多少"。

思路

（官方题解给出了把任意礼物序列化简为"好序列"的核心引理；本题解在此基础上补充完整的数据结构与查询方法。）

把礼物序列 $P=(P_1,\dots,P_M)$ 视为一个函数 $t_P(T)$ ：输入初始心情 $T$ ，输出收完所有礼物后的心情。记 $|P|=M$ 。

好序列：称序列 $P$ 是好的，如果对所有 $i$ 都成立 $P_i+A\le P_{i+1}$ 。好序列有一个关键性质：

存在阈值 $i_C$ ，使得第 $i<i_C$ 件礼物全部让他失望，第 $i\ge i_C$ 件礼物全部让他开心。

证明：一旦在某件礼物上开心（此时 $T_i\le P_i$ ），下一件礼物前的心情 $T_{i+1}=T_i+A\le P_i+A\le P_{i+1}$ ，所以下一件仍然开心。可见"开心"一旦开始就不会停止。

对好序列，若前 $i-1$ 件都失望，则第 $i$ 件礼物前的心情为 $T-(i-1)B$ 。它在第 $i$ 件失望当且仅当

T-(i-1)B>P_i\iff T>P_i+(i-1)B.

记 $R_i=P_i+(i-1)B$ 。由 $R_{i+1}-R_i=(P_{i+1}-P_i)+B\ge A+B>0$ 知 $R$ 严格递增，所以失望次数

c(T)=\#\{i:R_i<T\},

最终心情为

t_P(T)=T-cB+(M-c)A=T+MA-c(A+B).

这样对固定的好序列，一次询问只需在 $R$ 序列上二分求 $c$ 。

任意序列可以化简为等价的好序列：官方题解证明了长度 2 的变换：若相邻对 $(p,q)$ 不好（即 $q-A<p$ ），则

(p,q)\ \text{与}\ \big(q-A,\ \max\{q,\ p-B\}\big)

对一切 $T$ 的最终心情相同（等价），且后者一定是好序列（因为 $(q-A)+A=q\le\max\{q,p-B\}$ ）。于是：给定一个已好的序列，在末尾追加 $q$ 之后，从后往前不断把"不好的相邻对"替换为等价的好对，最终得到的仍是与原序列等价的好序列。我们也用同样的方法构建初始序列：把初始 $N$ 件礼物逐个追加进空的好序列。

如何高效维护：直接逐对替换最坏每次 $O(M)$ ，需要数据结构。核心结论是：向好序列追加 $q$ 的效果等价于"用一条等差数列段替换序列的一个后缀"，具体如下。

令 $Z_i=P_i-iA$ 。好序列等价于 $Z$ 非递减。对当前长度 $M$ 的好序列追加 $q$ ，令

\theta=q-(M+1)A.

设 $j^*$ 为满足 $Z_j\le\theta$ 的最大下标（若不存在则为 0），再设 $i_0$ 为满足 $Z_i\le\theta+A+B$ 的最大下标（注意 $i_0\ge j^*$ ）。则新序列为：

前 $j^*$ 个元素不变；
位置 $j^*+1,\dots,i_0+1$ 是一段等差数列，值依次为

q-(M-j^*)A,\ q-(M-j^*-1)A,\ \dots,

步长为 $A$ ；

之后接原序列位置 $i_0+1,\dots,M$ ，每个值再减 $B$ 。

（上述结论可由官方的逐对替换推得：替换 $k$ 次后序列形如

\big(P_1,\dots,P_{M-k},\ q-kA,\ \max\{q-(k-1)A,P_{M-k+1}-B\},\dots,\max\{q,P_M-B\}\big),

把" $\max$ 与等差数列"合并整理即得上面的形式。）

因此可以用一棵隐式 treap 维护好序列，每个节点是一个"等差数列段"（记录段首值 $s$ 与段长 $\ell$ ，步长恒为 $A$ ）。需要支持：

二分求 $j^*$ ：条件 $Z_j=P_j-jA\le\theta$ 等价于 $P_j+(M+1-j)A\le q$ 。对每个段这个量是常数（段内 $P$ 以步长 $A$ 递增），且全序列单调不减，因此在 treap 上沿单条路径下降统计即可， $O(\log)$ ；
二分求 $i_0$ ：条件 $P_i+(M-i)A\le q+A+2B$ ，同理是段内常数、整体单调；
区间加法：对保留下来的后缀整体减 $B$ ，打懒标记即可；
整体插入一条等差段：每次追加只新建 1 个节点，所以总节点数为 $O(N+Q)$ 。

这样每次追加、每次询问都是 $O(\log(N+Q))$ ，总复杂度 $O((N+Q)\log(N+Q))$ 。

询问时，在 treap 上统计满足 $R_i=P_i+(i-1)B<T$ 的下标个数 $c$ （段内 $R$ 以步长 $A+B$ 递增，段内计数可用整除公式一次算清），然后输出

T+MA-c(A+B).

数值规模最大约 $4\times 10^{14}$ ，务必使用 long long（样例 2 的答案甚至达到 $10^{12}$ 量级）。

参考代码

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

struct Node {
    ll s;       // start P-value of the segment
    ll len;     // number of elements in this segment
    ll sz;      // total elements in subtree
    ll lazy;    // pending add to s of every segment in subtree
    int pri;
    Node *l, *r;
    Node(ll s_, ll len_) : s(s_), len(len_), sz(len_), lazy(0), l(nullptr), r(nullptr) {
        static mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
        pri = (int)rng();
    }
};

ll sz(Node* t) { return t ? t->sz : 0; }

void push(Node* t) {
    if (!t || t->lazy == 0) return;
    t->s += t->lazy;
    if (t->l) t->l->lazy += t->lazy;
    if (t->r) t->r->lazy += t->lazy;
    t->lazy = 0;
}

void pull(Node* t) {
    if (!t) return;
    t->sz = sz(t->l) + t->len + sz(t->r);
}

void split(Node* t, ll k, Node*& a, Node*& b) {
    if (!t) { a = b = nullptr; return; }
    push(t);
    if (k <= sz(t->l)) {
        split(t->l, k, a, t->l);
        b = t; pull(b);
    } else {
        split(t->r, k - sz(t->l) - t->len, t->r, b);
        a = t; pull(a);
    }
}

Node* merge(Node* a, Node* b) {
    if (!a) return b;
    if (!b) return a;
    if (a->pri > b->pri) {
        push(a);
        a->r = merge(a->r, b);
        pull(a);
        return a;
    } else {
        push(b);
        b->l = merge(a, b->l);
        pull(b);
        return b;
    }
}

// count of positions (absolute, 1-indexed) with key = s + (M+1-a)*A <= q
ll walkJ(Node* t, ll base, ll M, ll A, ll q) {
    if (!t) return 0;
    push(t);
    ll a = base + 1 + sz(t->l);
    ll key = t->s + (M + 1 - a) * A;
    if (key <= q)
        return sz(t->l) + t->len + walkJ(t->r, base + sz(t->l) + t->len, M, A, q);
    else
        return walkJ(t->l, base, M, A, q);
}

// count of positions with key2 = s + (M-a)*A <= thresh
ll walkC(Node* t, ll base, ll M, ll A, ll thresh) {
    if (!t) return 0;
    push(t);
    ll a = base + 1 + sz(t->l);
    ll key = t->s + (M - a) * A;
    if (key <= thresh)
        return sz(t->l) + t->len + walkC(t->r, base + sz(t->l) + t->len, M, A, thresh);
    else
        return walkC(t->l, base, M, A, thresh);
}

// count of positions with R = s + (a-1)*B < T
ll walkY(Node* t, ll base, ll T, ll A, ll B) {
    if (!t) return 0;
    push(t);
    ll a = base + 1 + sz(t->l);
    ll Ra = t->s + (a - 1) * B;
    if (Ra >= T)
        return walkY(t->l, base, T, A, B);
    else {
        ll cnt = min(t->len, (T - 1 - Ra) / (A + B) + 1);
        return sz(t->l) + cnt + walkY(t->r, base + sz(t->l) + t->len, T, A, B);
    }
}

void append(Node*& root, ll q, ll A, ll B) {
    ll M = root ? root->sz : 0;
    ll jstar = walkJ(root, 0, M, A, q);
    if (jstar == M) {                       // already good: no replacement needed
        root = merge(root, new Node(q, 1));
        return;
    }
    Node *L, *R;
    split(root, jstar, L, R);               // R = old positions jstar+1 .. M
    ll cR = walkC(R, jstar, M, A, q + 2 * B);  // positions to discard (a prefix of R)
    Node *R1, *R2;
    split(R, cR, R1, R2);                   // discard R1, keep R2 with a shift of -B
    (void)R1;
    if (R2) R2->lazy += -B;
    ll startVal = q - (M - jstar) * A;      // the new arithmetic-progression segment
    Node* line = new Node(startVal, cR + 1);
    root = merge(merge(L, line), R2);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll N, A, B;
    cin >> N >> A >> B;
    Node* root = nullptr;
    for (int i = 0; i < N; i++) {
        ll p;
        cin >> p;
        append(root, p, A, B);
    }
    int Q;
    cin >> Q;
    while (Q--) {
        ll T, X;
        cin >> T >> X;
        if (T == 1) {
            append(root, X, A, B);
        } else {
            ll M = root->sz;
            ll c = walkY(root, 0, X, A, B);
            cout << X + M * A - c * (A + B) << '\n';
        }
    }
    return 0;
}

复杂度分析

时间复杂度： $O((N+Q)\log(N+Q))$
空间复杂度： $O(N+Q)$