AtCoder Beginner Contest 434 题解

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

AtCoder Beginner Contest 434 题解

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

比赛概览

本场整体难度适中偏后置：A、B 是简单签到，C（300 分）是经典的"可行高度区间"贪心，思路非常典型；D（425 分）考察二维差分（imos）的灵活运用，把"覆盖数"和"覆盖云的编号和"两个差分数组一起做，颇具区分度；E（500 分）是一道漂亮的图论建模题，把跳跃过程转化为"给每条边染一个端点"；F（575 分）在经典的"拼接字典序最小"排序基础上要求输出第二小，且比较器有 O(N·|S|) 超时陷阱，需要用 Z 算法优化；G（650 分）是全场最难，线段树上存压缩信息并支持 $O(\log N)$ 的"提取末尾若干位"合并，值得深入掌握。

A - Balloon Trip

题目链接：https://atcoder.jp/contests/abc434/tasks/abc434_a

题目大意

给定高桥的体重 $W$ （单位 kg）和每个气球的升力 $B$ （单位 g）。挂上 $n$ 个气球后，若物体质量严格小于 $nB$ 克，就能飞上天空。求让高桥飞起来所需的最少气球数。

思路

先做单位换算： $W\ \text{kg} = 1000W\ \text{g}$ 。需要找到最小的整数 $n$ ，使得

1000W < nB.

解不等式得 $n > \dfrac{1000W}{B}$ ，因此最小的整数就是

n = \left\lfloor \frac{1000W}{B} \right\rfloor + 1.

关键在于"严格小于"：当 $1000W$ 恰好是 $B$ 的倍数时， $n = \frac{1000W}{B}$ 只会让气球总升力等于体重（不严格小于），必须再加 1。例如样例 1： $80\ \text{kg} = 80000\ \text{g}$ ， $B=5$ 时 $\lfloor 80000/5 \rfloor + 1 = 16001$ ，而 16000 个气球时 $16000 \times 5 = 80000$ 不严格小于，飞不起来。数据范围很小（ $W,B \le 100$ ），用循环从小到大枚举 $n$ 也一样可行。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int W, B;
    cin >> W >> B;
    cout << (1000 * W) / B + 1 << '\n';
    return 0;
}

复杂度分析

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

B - Bird Watching

题目链接：https://atcoder.jp/contests/abc434/tasks/abc434_b

题目大意

天空中有 $N$ 只鸟、共 $M$ 种类型，第 $i$ 只鸟的类型为 $A_i$ 、大小为 $B_i$ 。对每个类型 $k$ ，输出该类型所有鸟大小的平均值。保证每种类型至少有一只鸟。误差不超过 $10^{-5}$ 即算正确。

思路

数据范围很小（ $M \le N \le 100$ ），直接用桶统计即可。维护两个数组：

$S_k$ ：类型 $k$ 的所有鸟的大小之和；
$C_k$ ：类型 $k$ 的鸟的个数。

读入时对每只鸟执行 $S_{A_i} \gets S_{A_i} + B_i$ 、 $C_{A_i} \gets C_{A_i} + 1$ 。最后对每个 $k$ 输出 $S_k / C_k$ 。由于题目允许 $10^{-5}$ 的相对/绝对误差，输出时保留足够多的小数位（例如 setprecision(15)），避免精度问题。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, M;
    cin >> N >> M;
    vector<long long> sum(M + 1, 0), cnt(M + 1, 0);
    for (int i = 0; i < N; i++) {
        int a, b;
        cin >> a >> b;
        sum[a] += b;
        cnt[a]++;
    }
    cout << fixed << setprecision(15);
    for (int k = 1; k <= M; k++) {
        cout << (double)sum[k] / cnt[k] << '\n';
    }
    return 0;
}

复杂度分析

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

C - Flapping Takahashi

题目链接：https://atcoder.jp/contests/abc434/tasks/abc434_c

题目大意

高桥在时间 $0$ 位于高度 $H$ ，将飞行 $10^9$ 秒。他每秒最多改变高度 $1$ （即对任意 $0 \le t < u \le 10^9$ 有 $|F(u)-F(t)| \le u-t$ ），且任意时刻高度必须 $> 0$ 。有 $N$ 个目标：在时间 $t_i$ 时高度要落在 $[l_i, u_i]$ 内。问是否存在一条飞行轨迹满足全部目标。 $T$ 组测试，满足 $\sum N \le 10^5$ 。

思路

飞行的具体轨迹有无穷多种，直接构造不可行。关键观察：与其找一条路径，不如维护"当前时刻所有可行高度组成的集合"，可以证明这个集合一定是一个区间 $[L, U]$ （或者为空）。

从时刻 $t_{i-1}$ 到 $t_i$ 经过了 $d = t_i - t_{i-1}$ 秒。由于每秒最多移动 $1$ ，区间两端向外各扩张 $d$ ：

L \gets L - d, \qquad U \gets U + d.

同时高度必须 $> 0$ 。这里有一个细节：原题要求高度严格大于 0，而不是 $\ge 1$ 。但因为所有目标的 $l_i \ge 1$ ，把约束改成"高度 $\ge 1$ "并不会改变可行性——两条约束下可达高度区间的下界至多为 $1$ ，而任何一个目标要求的 $l_i \ge 1$ ，取交集后下界依然由 $l_i$ 决定。因此直接令

L \gets \max(L, 1).

再与第 $i$ 个目标的要求取交集：

L \gets \max(L, l_i), \qquad U \gets \min(U, u_i).

若某一步之后 $L > U$ ，说明可行集合为空，答案即 No；否则继续处理。所有目标处理完后可行集合非空，答案即 Yes。

正确性：上述过程对"可达集合"做的是精确的区间运算——扩张对应速度限制、取交集对应目标约束，二者都不会破坏"可达集合恰为一个区间"这一不变量，因此可以按时间顺序贪心处理，不需要回溯。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int N;
        ll H;
        cin >> N >> H;
        ll tPrev = 0, L = H, U = H;
        bool ok = true;
        for (int i = 0; i < N; i++) {
            ll t, l, u;
            cin >> t >> l >> u;
            ll d = t - tPrev;
            tPrev = t;
            L -= d;
            U += d;
            L = max(L, 1LL);   // 高度必须 > 0，等价于 >= 1
            L = max(L, l);
            U = min(U, u);
            if (L > U) ok = false;
        }
        cout << (ok ? "Yes" : "No") << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度：每组 $O(N)$ ，总 $O(\sum N)$
空间复杂度： $O(1)$

D - Clouds

题目链接：https://atcoder.jp/contests/abc434/tasks/abc434_d

题目大意

天空是 $2000 \times 2000$ 的网格，有 $N$ 朵云，第 $i$ 朵云覆盖矩形 $U_i \le r \le D_i$ 、 $L_i \le c \le R_i$ 。对每个 $k=1,\dots,N$ ，问：只移除云 $k$ 后，不被任何云覆盖的格子数是多少？

思路

记 $C_0$ 为"不被任何云覆盖的格子数"， $C_k$ 为"恰好只被云 $k$ 覆盖的格子数"。移除云 $k$ 后，原来属于 $C_0$ 的格子仍然不被覆盖，原来只被云 $k$ 覆盖的格子变成不被覆盖，其余格子仍被至少一朵云覆盖。因此答案是

C_0 + C_k.

于是问题拆成两步：统计每个格子被多少朵云覆盖；以及对于"恰好被 1 朵云覆盖"的格子，识别出是哪朵云。

二维差分（二维 imos）统计覆盖数。 对覆盖 $[U,D] \times [L,R]$ 的矩形，在差分数组 $A$ 上做四次单点修改：

A[U][L] += 1,\quad A[U][R+1] -= 1,\quad A[D+1][L] -= 1,\quad A[D+1][R+1] += 1.

对 $N$ 朵云全部处理完后，先按行做前缀和，再按列做前缀和， $A[r][c]$ 就是格子 $(r,c)$ 被覆盖的次数。

识别唯一覆盖的云。 再开一个差分数组 $B$ ，每次给矩形加的不是 $1$ 而是云的编号 $k$ 。做完同样的前缀和后，若 $A[r][c] = 1$ ，则 $B[r][c]$ 恰好就是覆盖该格子那朵云的编号（因为只有这一朵云向 $B$ 贡献了值）。

最后统计： $C_0$ 为 $A[r][c] = 0$ 的格子数； $C_k$ 为 $A[r][c] = 1$ 且 $B[r][c] = k$ 的格子数。依次输出 $C_0 + C_k$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    const int S = 2000;
    int N;
    cin >> N;
    vector<vector<ll>> cnt(S + 2, vector<ll>(S + 2, 0));
    vector<vector<ll>> sum(S + 2, vector<ll>(S + 2, 0));
    for (int k = 1; k <= N; k++) {
        int u, d, l, r;
        cin >> u >> d >> l >> r;
        cnt[u][l]++;
        cnt[u][r + 1]--;
        cnt[d + 1][l]--;
        cnt[d + 1][r + 1]++;
        sum[u][l] += k;
        sum[u][r + 1] -= k;
        sum[d + 1][l] -= k;
        sum[d + 1][r + 1] += k;
    }
    // 横向前缀和
    for (int i = 1; i <= S + 1; i++)
        for (int j = 1; j <= S + 1; j++) {
            cnt[i][j] += cnt[i][j - 1];
            sum[i][j] += sum[i][j - 1];
        }
    // 纵向前缀和
    for (int i = 1; i <= S + 1; i++)
        for (int j = 1; j <= S + 1; j++) {
            cnt[i][j] += cnt[i - 1][j];
            sum[i][j] += sum[i - 1][j];
        }
    vector<ll> bk(N + 1, 0);
    for (int i = 1; i <= S; i++)
        for (int j = 1; j <= S; j++) {
            if (cnt[i][j] == 0) bk[0]++;
            else if (cnt[i][j] == 1) bk[sum[i][j]]++;
        }
    for (int k = 1; k <= N; k++)
        cout << bk[0] + bk[k] << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(S^2 + N)$ ，其中 $S = 2000$
空间复杂度： $O(S^2)$

E - Distribute Bunnies

题目链接：https://atcoder.jp/contests/abc434/tasks/abc434_e

题目大意

数轴上有 $N$ 只兔子，第 $i$ 只在坐标 $X_i$ ，跳跃力为 $R_i$ 。每只兔子恰好跳一次，跳到 $X_i + R_i$ 或 $X_i - R_i$ 。可以任意为每只兔子选择落点，求跳跃后"兔子所在的互异坐标"的最大数量。

思路

把每个坐标看作图的顶点。对每只兔子 $i$ ，在顶点 $X_i - R_i$ 与 $X_i + R_i$ 之间连一条无向边。由于 $R_i \ge 1$ ，两个端点必然不同（没有自环）。

在这个图里，"给每只兔子选落点"等价于"给每条边染一个端点"（同一个顶点可以被多条边染到）。我们要最大化被染到至少一次的顶点数。不同连通分量互不影响，因此逐分量求解。

设一个连通分量有 $n$ 个顶点、 $m$ 条边（重边也要计入：两条边对应两只兔子）：

分量是树（ $m = n-1$ ）。每条边至多贡献 1 个此前未被染的顶点，所以染到的顶点数至多为 $m = n-1$ 。而这是可以做到的：任取一个根把树定向，每条边都染"子端点"，则除根以外的 $n-1$ 个顶点全部被染。故该分量贡献 $n-1$ 。
分量不是树（ $m \ge n$ ）。分量内总共只有 $n$ 个顶点，最多染到 $n$ 个。构造达到 $n$ 的方案：取生成树 $T$ ，任取一条不在 $T$ 中的边 $uv$ 。把 $T$ 以 $v$ 为根定向，每条树边染子端点，此时除 $v$ 外所有顶点都被染到；最后用多余的边 $uv$ 把 $v$ 也染上。故该分量贡献 $n$ 。

因此算法很简单：对每个含边的连通分量统计顶点数 $n$ 与边数 $m$ ，若 $m = n-1$ 则累加 $n-1$ ，否则累加 $n$ 。坐标绝对值可达 $2 \times 10^9$ ，先离散化再建图；DFS/BFS 遍历时用标记数组保证每条边只统计一次（这样重边会被正确计入 $m$ ）。

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    vector<ll> X(N), R(N);
    vector<ll> coords;
    coords.reserve(2 * N);
    for (int i = 0; i < N; i++) {
        cin >> X[i] >> R[i];
        coords.push_back(X[i] - R[i]);
        coords.push_back(X[i] + R[i]);
    }
    sort(coords.begin(), coords.end());
    coords.erase(unique(coords.begin(), coords.end()), coords.end());
    int M = coords.size();
    vector<vector<pair<int, int>>> g(M);  // (邻接顶点, 边编号)
    for (int i = 0; i < N; i++) {
        int a = lower_bound(coords.begin(), coords.end(), X[i] - R[i]) - coords.begin();
        int b = lower_bound(coords.begin(), coords.end(), X[i] + R[i]) - coords.begin();
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }
    vector<int> vis(M, 0);
    vector<char> used(N, 0);
    long long ans = 0;
    for (int s = 0; s < M; s++) {
        if (vis[s]) continue;
        ll n = 0, m = 0;
        stack<int> stk;
        stk.push(s);
        vis[s] = 1;
        while (!stk.empty()) {
            int v = stk.top();
            stk.pop();
            n++;
            for (auto [to, eid] : g[v]) {
                if (!used[eid]) { used[eid] = 1; m++; }
                if (!vis[to]) { vis[to] = 1; stk.push(to); }
            }
        }
        ans += (m == n - 1) ? (n - 1) : n;
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

时间复杂度： $O(N \log N)$ （坐标排序与二分查找）
空间复杂度： $O(N)$

F - Concat (2nd)

题目链接：https://atcoder.jp/contests/abc434/tasks/abc434_f

题目大意

给定 $N$ 个字符串 $S_i$ 。把所有排列 $P = (P_1,\dots,P_N)$ 对应拼接出的字符串 $S_{P_1} S_{P_2} \dots S_{P_N}$ 收集起来，按字典序从小到大排成 $A_1, A_2, \dots, A_{N!}$ 。输出 $A_2$ （第二小）。 $T$ 组数据，满足 $\sum N \le 3 \times 10^5$ 、 $\sum |S_i| \le 10^6$ 。

思路

第一步：找出最小拼接，用经典比较器。 定义

X < Y \iff XY < YX.

该比较器构成严格全序（传递性可用无限重复串说明： $XY < YX$ 当且仅当 $X^\infty$ 的字典序小于 $Y^\infty$ ，而无限串的字典序显然是全序）。按此比较器排序得到 $S'_1, S'_2, \dots, S'_N$ ，则 $S'_1 S'_2 \dots S'_N$ 是字典序最小的拼接——用交换论证：若最优排列中相邻两项 $A, B$ 不满足比较器（即 $AB > BA$ ），交换它们后拼接串变小，故最优排列必满足相邻有序。

第二步：第二小的结构。 若存在相邻对满足 $S'_i S'_{i+1} = S'_{i+1} S'_i$ （并列），则交换它们得到完全相同的串，故 $A_1 = A_2 = S'_1 \dots S'_N$ ，直接输出。

否则任意相邻对严格不等。对任一排列，交换一对相邻的逆序对会使拼接串严格变小（对应比较器 $XY > YX$ ）。因此逆序数 $\ge 2$ 的排列至少有 2 个严格比它小的串，不可能是 $A_2$ 。故 $A_2$ 必为"仅交换排序后某一对相邻元素"的排列。

再比较这些相邻交换：设 $P_i$ 为交换位置 $i, i+1$ 得到的排列（ $1 \le i \le N-1$ ）。交换位置越靠左，拼接串与前缀出现差异的位置越早，串越大。具体地，只要 $i \le N-3$ ，就有 $P_{N-1} < P_i$ ：两者在位置 $i$ 首次不同，而 $S'_i < S'_{i+1}$ 蕴含 $S'_i S'_{i+1} < S'_{i+1} S'_i$ ，故 $P_i$ 更大。所以只需在最后两个相邻交换中取较小者：

c_1 = S'_1 \cdots S'_{N-2}\, S'_N \, S'_{N-1}, \qquad c_2 = S'_1 \cdots S'_{N-3}\, S'_{N-1}\, S'_{N-2}\, S'_N,

答案为 $\min(c_1, c_2)$ 。 $N = 2$ 时特判，输出 $S'_2 S'_1$ 。

第三步：用 Z 数组优化比较器（本题的关键陷阱）。 朴素构造 $XY$ 与 $YX$ 比较需要 $O(|X| + |Y|)$ 。排序过程中一个很长的字符串可能被参与比较 $O(N)$ 次，总复杂度可达 $\Omega(N|S_i|)$ ，必超时。因此要把单次比较优化到 $O(\min(|X|,|Y|))$ 。

对每个字符串 $X$ 预处理 Z 数组： $Z_X[i]$ 表示 $X[i..]$ 与 $X$ 本身的最长公共前缀长度。假设 $|X| \ge |Y|$ ，比较 $XY$ 与 $YX$ ：

先逐位比较 $X$ 的前 $|Y|$ 个字符与 $Y$ （代价 $O(|Y|)$ ），若不同直接返回结果；
若前 $|Y|$ 个字符全部相等，即 $X[0..|Y|-1] = Y$ ，此时 $XY = Y\, X[|Y|..]\, Y, \qquad YX = Y\, Y\, X[|Y|..].$ 问题归结为比较 $X[|Y|..|X|-1]$ 与 $X[0..|X|-|Y|-1]$ （长度都为 $|X|-|Y|$ ）。利用 Z 数组 $O(1)$ 判定：若 $Z_X[|Y|] \ge |X|-|Y|$ 则两段相等，继续第 3 步；否则两段在 $Z_X[|Y|]$ 处首次不同，直接比较这两个字符即可确定大小；
若第 2 步判定相等，还需要比较末尾的 $Y$ 与 $X[|X|-|Y|..|X|-1]$ （长度都为 $|Y|$ ），逐位扫描 $O(|Y|)$ 。

$|X| < |Y|$ 时对称处理。这样每次比较代价为 $O(\min(|X|,|Y|))$ ，整个排序的复杂度为 $O(\sum |S_i| \log N)$ 。判断并列、拼接候选串等步骤的总代价也都是 $O(\sum |S_i|)$ 。

参考代码

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

vector<int> z_algorithm(const string& s) {
    int n = (int)s.size();
    vector<int> z(n);
    z[0] = n;
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i <= r) z[i] = min(r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
    }
    return z;
}

using psv = pair<string, vector<int>>;  // (字符串, 该串的 Z 数组)

// 比较 XY 与 YX，单次 O(min(|X|,|Y|))
bool comp(const psv& x, const psv& y) {
    const string& xs = x.first;
    const string& ys = y.first;
    const vector<int>& zx = x.second;
    const vector<int>& zy = y.second;
    int xl = (int)xs.size(), yl = (int)ys.size();
    if (xl >= yl) {
        for (int i = 0; i < yl; i++)
            if (xs[i] != ys[i]) return xs[i] < ys[i];
        if (xl != yl && zx[yl] < xl - yl)
            return xs[yl + zx[yl]] < xs[zx[yl]];
        for (int i = 0; i < yl; i++)
            if (ys[i] != xs[i + (xl - yl)]) return ys[i] < xs[i + (xl - yl)];
    } else {
        for (int i = 0; i < xl; i++)
            if (xs[i] != ys[i]) return xs[i] < ys[i];
        if (zy[xl] < yl - xl)
            return ys[zy[xl]] < ys[xl + zy[xl]];
        for (int i = 0; i < xl; i++)
            if (ys[i + (yl - xl)] != xs[i]) return ys[i + (yl - xl)] < xs[i];
    }
    return false;  // XY == YX（并列）
}

string concat(const vector<psv>& s) {
    string res;
    for (auto& nx : s) res += nx.first;
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        vector<psv> s(N);
        for (auto& nx : s) {
            cin >> nx.first;
            nx.second = z_algorithm(nx.first);
        }
        sort(s.begin(), s.end(), comp);

        if (N == 2) {
            cout << s[1].first + s[0].first << '\n';
            continue;
        }
        bool tie = false;
        for (int i = 1; i < N; i++)
            if (s[i - 1].first + s[i].first == s[i].first + s[i - 1].first) {
                tie = true;
                break;
            }
        if (tie) {
            cout << concat(s) << '\n';
            continue;
        }
        swap(s[N - 1], s[N - 2]);
        string c1 = concat(s);
        swap(s[N - 1], s[N - 2]);
        swap(s[N - 2], s[N - 3]);
        string c2 = concat(s);
        cout << min(c1, c2) << '\n';
    }
    return 0;
}

复杂度分析

时间复杂度： $O(\sum |S_i| \log N)$
空间复杂度： $O(\sum |S_i|)$

G - Keyboard

题目链接：https://atcoder.jp/contests/abc434/tasks/abc434_g

题目大意

字符串 $S$ 由 1-9 和 B 组成。定义 $f(A)$ ：从空串 $C$ 出发按顺序处理 $A$ 的每个字符，数字追加到 $C$ 末尾，B 删除 $C$ 的最后一个字符（ $C$ 为空则无事发生）。处理 $Q$ 个操作：

1 x c：把 $S_x$ 改成 $c$ ；
2 l r：令 $T = S_l \dots S_r$ ， $U = f(T)$ 。若 $U$ 为空输出 -1，否则输出 $U$ 按十进制对 $998244353$ 取模的值。

约束 $N \le 8 \times 10^6$ 、 $Q \le 2 \times 10^5$ ，时间限制很紧。

思路

规范化与幺半群。 定义 $\mathrm{normalize}(S)$ ：不断删除 $S$ 中形如"数字 + B"的子串，直到不能再删。它满足

\mathrm{normalize}(S+T) = \mathrm{normalize}\big(\mathrm{normalize}(S) + \mathrm{normalize}(T)\big),

即规范化后的字符串关于拼接构成幺半群（空串为单位元）。而且 $f(S)$ 正是 $\mathrm{normalize}(S)$ 去掉开头所有 B 后的数字串。这提示我们用线段树，每个节点存其区间规范化后的结果。但规范化结果的长度可能达到 $O(N)$ ，直接存必超时。

把每个节点的信息压缩成三元组 $(b, l, x)$ ：

$b$ ：规范化串中开头 B 的个数；
$l$ ：去掉开头 B 后数字部分的长度，即 $|f(\cdot)|$ ；
$x$ ：该数字部分按十进制对 $998244353$ 取模的值。

合并两个节点。 设左操作数的规范化串为 $B^{b_L} g_L$ ，右操作数为 $B^{b_R} g_R$ （ $g$ 表示数字部分）。拼接后为 $B^{b_L} g_L B^{b_R} g_R$ ，右操作数开头的 $b_R$ 个 B 会依次删掉 $g_L$ 末尾的 $b_R$ 个数字：

若 $b_R \le l_L$ ： $b = b_L, \qquad l = l_L - b_R + l_R, \qquad x = \mathrm{val}\!\left(g_L \text{ 去掉末尾 } b_R \text{ 个数字}\right) \cdot 10^{l_R} + x_R.$
若 $b_R > l_L$ ： $g_L$ 被完全删光，多余的 $b_R - l_L$ 个 B 现在紧跟在 $g_R$ 前面，会与原有的 $b_L$ 个开头 B 连成一片，因此 $b = b_L + b_R - l_L, \qquad l = l_R, \qquad x = x_R.$

注意第一种情形需要"数字部分去掉末尾 $b_R$ 位后的值"，也就是需要知道 $g_L$ 末尾若干位的具体值——这恰恰是 $(b,l,x)$ 三元组丢失的信息。

关键技巧：从线段树上 $O(\log N)$ 提取"末尾 $n$ 位"。 本题的精妙之处在于：只要左操作数存储在线段树上，就能在 $O(\log N)$ 内求出其数字部分末尾 $n$ 个数字组成的整数，从而完成一次合并。

设节点 $i$ 的规范化串为 $B^{b_i} + A_i$ （ $A_i$ 为数字部分， $|A_i| = l_i$ ，值为 $x_i$ ）。它的右孩子 $rc$ 满足 $A_i = A'_{lc} + A_{rc}$ ，其中 $A'_{lc}$ 是左孩子数字部分 $A_{lc}$ 删掉末尾 $b_{rc}$ 个数字后的串。要求 $A_i$ 末尾 $n$ 个数字的值：

若 $n = 0$ ，返回 0；若 $n = l_i$ ，返回 $x_i$ ；
若 $n \le l_{rc}$ ，递归到右孩子；
否则还需 $m = n - l_{rc}$ 个数字，它们来自 $A'_{lc}$ 的末尾。因为 $A'_{lc}$ 是 $A_{lc}$ 去掉末尾 $b_{rc}$ 个数字，等价于取 $A_{lc}$ 的末尾 $m + b_{rc}$ 个数字（值为 $y$ ），再去掉其中末尾 $b_{rc}$ 个（值为 $z$ ）。其中 $z = x_{lc} - \big((x_i - x_{rc}) \cdot 10^{-l_{rc}}\big) \cdot 10^{b_{rc}} \pmod{998244353},$ 依据是 $x_i = \mathrm{val}(A'_{lc}) \cdot 10^{l_{rc}} + x_{rc}$ 。于是想要的结果为 $\big((y - z) \cdot 10^{-b_{rc}} \cdot 10^{l_{rc}} + x_{rc}\big) \bmod 998244353.$ 递归深度不超过树高，故为 $O(\log N)$ 。

建树 / 修改 / 查询。 线段树采用堆式存储（节点 $i$ 的孩子为 $2i$ 与 $2i+1$ ，根为 $1$ ，叶子放单字符：数字 c 对应 $(0, 1, c)$ ，B 对应 $(1, 0, 0)$ ）。

建树：自底向上合并。第 $k$ 层（从叶子往上数）约有 $N / 2^k$ 个节点，每个节点合并时提取操作的下沉深度不超过 $k$ ，总代价 $\sum_k \frac{N}{2^k} \cdot k = O(N)$ 。
单点修改：改叶子后沿祖先链向上合并，每次合并 $O(\log N)$ ，总 $O(\log^2 N)$ 。
区间查询：把 $[l, r]$ 分解成 $O(\log N)$ 个线段树节点，从右往左依次合并（每次都保证左操作数是在树上的节点，从而可以调用上面的提取过程），每次合并 $O(\log N)$ ，总 $O(\log^2 N)$ 。最后若结果的 $l = 0$ 输出 -1，否则输出 $x$ 。

参考代码

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

const int MOD = 998244353;

struct Data {
    int b;  // 规范化串中开头 B 的个数
    int l;  // 数字部分长度（即 f() 的长度）
    int x;  // 数字部分 mod MOD 的值
};

vector<Data> seg;
vector<int> TEN, ITEN;  // 10^i 与 10^{-i} mod MOD

long long modpow(long long a, long long e) {
    long long r = 1;
    while (e) {
        if (e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

// 节点 i 的数字部分末尾 n 个数字组成的整数 mod MOD（0 <= n <= seg[i].l）
int lastDigits(int i, int n) {
    if (n == 0) return 0;
    if (n == seg[i].l) return seg[i].x;
    int lc = i * 2, rc = i * 2 + 1;
    if (seg[rc].l >= n) return lastDigits(rc, n);
    int m = n - seg[rc].l;        // 还缺的 m 个数字来自左孩子
    int b = seg[rc].b;            // 右孩子开头的 B 会删掉左孩子末尾 b 个数字
    int y = lastDigits(lc, m + b);
    long long z = (seg[lc].x - (long long)(seg[i].x - seg[rc].x + MOD) % MOD * ITEN[seg[rc].l] % MOD * TEN[b]) % MOD;
    if (z < 0) z += MOD;
    long long res = ((long long)(y - z + MOD) % MOD * ITEN[b] % MOD * TEN[seg[rc].l] + seg[rc].x) % MOD;
    return (int)res;
}

// 合并：左操作数是线段树节点 leftNode，右操作数是任意 Data r
Data combine(int leftNode, const Data& r) {
    if (r.b <= seg[leftNode].l) {
        int z = lastDigits(leftNode, r.b);   // 左数字部分末尾 r.b 个数字的值
        long long pref = ((long long)seg[leftNode].x - z + MOD) % MOD * ITEN[r.b] % MOD;
        Data d;
        d.b = seg[leftNode].b;
        d.l = seg[leftNode].l - r.b + r.l;
        d.x = (pref * TEN[r.l] + r.x) % MOD;
        return d;
    } else {
        // 左数字部分被全部删除，多余的 B 并入开头的 B 中
        return Data{seg[leftNode].b + r.b - seg[leftNode].l, r.l, r.x};
    }
}

void pull(int i) { seg[i] = combine(i * 2, seg[i * 2 + 1]); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, Q;
    cin >> N >> Q;
    string S;
    cin >> S;

    int SZ = 1;
    while (SZ < N) SZ <<= 1;
    seg.assign(2 * SZ, Data{0, 0, 0});
    for (int i = 0; i < N; i++) {
        int node = SZ + i;
        if (S[i] == 'B') seg[node].b = 1;
        else { seg[node].l = 1; seg[node].x = S[i] - '0'; }
    }
    TEN.assign(N + 1, 1);
    ITEN.assign(N + 1, 1);
    long long inv10 = modpow(10, MOD - 2);
    for (int i = 1; i <= N; i++) {
        TEN[i] = (long long)TEN[i - 1] * 10 % MOD;
        ITEN[i] = (long long)ITEN[i - 1] * inv10 % MOD;
    }
    for (int i = SZ - 1; i >= 1; i--) pull(i);

    while (Q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int x;
            char c;
            cin >> x >> c;
            --x;
            int node = SZ + x;
            seg[node] = Data{0, 0, 0};
            if (c == 'B') seg[node].b = 1;
            else { seg[node].l = 1; seg[node].x = c - '0'; }
            for (node >>= 1; node >= 1; node >>= 1) pull(node);
        } else {
            int l, r;
            cin >> l >> r;
            --l;  // 转成半开区间 [l, r)
            vector<int> ln, rn;
            int a = SZ + l, b = SZ + r;
            while (a < b) {
                if (a & 1) ln.push_back(a++);
                if (b & 1) rn.push_back(--b);
                a >>= 1; b >>= 1;
            }
            vector<int> nodes = ln;  // 从左到右排列的覆盖节点
            for (int i = (int)rn.size() - 1; i >= 0; i--) nodes.push_back(rn[i]);
            Data res = seg[nodes.back()];
            for (int i = (int)nodes.size() - 2; i >= 0; i--) res = combine(nodes[i], res);
            if (res.l == 0) cout << -1 << '\n';
            else cout << res.x << '\n';
        }
    }
    return 0;
}

复杂度分析

建树 $O(N)$ ；每次修改/查询 $O(\log^2 N)$ ，总时间复杂度 $O(N + Q \log^2 N)$
空间复杂度： $O(N)$ （线段树节点 $O(N)$ ， $10^i$ 与 $10^{-i}$ 的预计算表各 $O(N)$ ）