AtCoder Beginner Contest 441 题解

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

比赛概览

本场难度梯度合理：A、B 为纯签到题，C 是一道经典的"最坏情况 + 排序贪心"问题，D 依赖出度 $\le 4$、步数 $L \le 10$ 的小约束直接 DFS 爆搜，E 是前缀差分 + 顺序统计量的计数题（$C$ 字符是障眼法），F 是需要"前缀 DP + 后缀 DP"互相配合的 0/1 背包分类题，G 则是考察懒标记线段树（区间翻转 + 区间加 + 区间最大值）的压轴题。E、F、G 三道题较有区分度，分别涉及计数转化、背包双端拼接与带翻转的懒标记线段树设计，值得重点掌握。

---

A - Black Square

题目链接：https://atcoder.jp/contests/abc441/tasks/abc441_a

题目大意

有一个 $10^{100} \times 10^{100}$ 的巨大网格。其中只有以 $(P,Q)$ 为左上角的 $100 \times 100$ 矩形区域被涂黑，其余全是白色。判断格子 $(X,Y)$ 是否被涂黑。输入两行 $P\ Q$ 与 $X\ Y$，输出 Yes 或 No。

思路

黑色区域由第 $P$ 行到第 $P+99$ 行、第 $Q$ 列到第 $Q+99$ 列组成。因此 $(X,Y)$ 为黑色的充要条件是

$$P \le X < P+100 \quad \text{且} \quad Q \le Y < Q+100 .$$

易错点：黑色区域一共是 $100$ 行/列，所以右边界是"开区间"$< P+100$（等价地 $\le P+99$）。若写成 $P \le X \le P+100$，就会把第 $P+100$ 行（这一行已经是白色）错误地算进来，导致答案错误。

实现时直接对这两个条件用 if 判断即可，无需任何复杂结构。

参考代码

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

int main() {
    int P, Q, X, Y;
    cin >> P >> Q;
    cin >> X >> Y;
    if (P <= X && X < P + 100 && Q <= Y && Y < Q + 100)
        cout << "Yes\n";
    else
        cout << "No\n";
    return 0;
}

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

p, q = map(int, input().split())
x, y = map(int, input().split())
if p <= x < p + 100 and q <= y < q + 100:
    print("Yes")
else:
    print("No")

复杂度分析

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

---

B - Two Languages

题目链接：https://atcoder.jp/contests/abc441/tasks/abc441_b

题目大意

AtCoder 国有两种官方语言 Takahashi-go 与 Aoki-go。Takahashi-go 只使用字符串 $S$ 中出现的字符（$|S|=N$），Aoki-go 只使用字符串 $T$ 中出现的字符（$|T|=M$）。$S$、$T$ 内的字符互不相同且按字典序排列。给定 $Q$ 个单词 $w_1,\dots,w_Q$，已知每个单词确实属于其中至少一种语言，判断每个单词属于哪一类：确定为 Takahashi-go 单词、确定为 Aoki-go 单词、或无法确定。

思路

关键观察：一个单词 $w$ 可能属于 Takahashi-go，当且仅当 $w$ 中出现的每一个字符都在 $S$ 中；对 Aoki-go 同理（只需把 $S$ 换成 $T$）。这里并不需要关心语言中"词的构成规则"，因为题意只告诉我们语言使用的字符集，能写出的单词就是由该字符集任意组合而成的字符串。

设

$$canT = \forall c \in w,\ c \in S, \qquad canA = \forall c \in w,\ c \in T .$$

由于题目保证 $w$ 至少属于一种语言，因此 $canT$ 与 $canA$ 至少一个为真。分类如下：

• $canT$ 为真且 $canA$ 为假：只能是 Takahashi-go，输出 Takahashi；
• $canA$ 为真且 $canT$ 为假：只能是 Aoki-go，输出 Aoki；
• 两者都为真：Unknown。

因为字母只有 $26$ 个，可以用两个长度 $26$ 的布尔数组记录 $S$、$T$ 中各有哪些字符，然后对每个单词逐字符 $O(1)$ 判断，非常简洁。

参考代码

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

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

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

    array<bool, 26> inS{}, inT{};
    for (char c : S) inS[c - 'a'] = true;
    for (char c : T) inT[c - 'a'] = true;

    int Q;
    cin >> Q;
    while (Q--) {
        string w;
        cin >> w;
        bool canT = true, canA = true;
        for (char c : w) {
            if (!inS[c - 'a']) canT = false;
            if (!inT[c - 'a']) canA = false;
        }
        if (canT && !canA) cout << "Takahashi\n";
        else if (canA && !canT) cout << "Aoki\n";
        else cout << "Unknown\n";
    }
    return 0;
}

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

n, m = map(int, input().split())
s = input()
t = input()
q = int(input())
for _ in range(q):
    w = input()
    can_t = all(c in s for c in w)
    can_a = all(c in t for c in w)
    if can_t and not can_a:
        print("Takahashi")
    elif can_a and not can_t:
        print("Aoki")
    else:
        print("Unknown")

复杂度分析

• 时间复杂度：$O(N + M + \sum_i |w_i|)$（用布尔数组的话每个字符 $O(1)$）
• 空间复杂度：$O(1)$（两个固定长度 $26$ 的数组）

---

C - Sake or Water

题目链接：https://atcoder.jp/contests/abc441/tasks/abc441_c

题目大意

有 $N$ 个杯子，第 $i$ 个杯子里装有 $A_i$ ml 无色透明液体。已知其中恰好 $K$ 杯是清酒，其余是水，但不知道具体哪几杯。Takahashi 可以任选若干个（至少一个）杯子并全部喝掉。问最少选多少个杯子，才能保证无论清酒在哪几个杯子里，他都能喝到至少 $X$ ml 清酒；若无论如何都不可能，输出 $-1$。

思路

这是典型的"最坏情况"分析问题。先把所有杯子的容量按从大到小排序：

$$A'_1 \ge A'_2 \ge \cdots \ge A'_N .$$

第一步：固定选 $M$ 个杯子，能保证的清酒量是多少？

水一共有 $N-K$ 杯。对手（也就是"选择清酒位置"的最坏情况）最想让我们喝到的清酒少，于是他会把容量最大的 $N-K$ 个杯子全部装满水。于是：

• 若 $M \le N-K$：对手可以让被选中的 $M$ 个杯子全是水，此时保证量是 $0$；
• 若 $M > N-K$：被选中的 $M$ 个杯子里至少有 $M-(N-K)$ 个是清酒。最坏情况下（容量最大的 $N-K$ 个杯子是水），被选中杯子中装清酒的是容量排名第 $N-K+1$ 大到第 $M$ 大的那些，因此保证量为

  $$A'_{N-K+1} + A'_{N-K+2} + \cdots + A'_M .$$

第二步：选 $M$ 个杯子时，保证量最大能到多少？

直观地想，为了让被选中杯子中"清酒部分"的容量和尽量大，应该选容量最大的 $M$ 个杯子。此时最坏情况下的清酒恰好是排名第 $N-K+1$ 到第 $M$ 的杯子，总量就是上式。而对任意其他 $M$ 个杯子的组合，其"清酒部分"（排除容量前 $N-K$ 大的杯子后剩下的那 $M-(N-K)$ 个杯子的容量和）不会超过"全体中除去前 $N-K$ 大后最大的 $M-(N-K)$ 个"的容量和，因此不可能更优。所以选 $M$ 个杯子时所能保证的最大清酒量就是：

$$f(M) = \begin{cases} 0, & M \le N-K,\\[2mm] \sum_{i=N-K+1}^{M} A'_i, & M > N-K . \end{cases}$$

第三步：求最小的 $M$ 使得 $f(M) \ge X$。

$f(M)$ 关于 $M$ 单调不减，从小到大扫描即可：维护一个前缀和 $sum$，从 $i=1$ 扫到 $N$，当 $i > N-K$ 时把 $A'_i$ 累加进 $sum$，一旦 $sum \ge X$ 就输出 $i$。若扫完 $N$ 个杯子仍 $sum < X$，说明连全部 $K$ 个最小的杯子（即最坏情况下唯一能保证装清酒的那些）加起来都不够 $X$，输出 $-1$。

注意：$X$ 与 $A_i$ 都很大（$X \le 3\times 10^{14}$），必须使用 64 位整数。

参考代码

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

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

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

    sort(A.begin(), A.end(), greater<ll>()); // 降序

    ll sum = 0;   // 累计保证的清酒量
    int ans = -1;
    for (int i = 0; i < N; ++i) {
        if (i >= N - K) sum += A[i];      // 排名 N-K+1 .. 的这些杯子才可能保证是清酒
        if (sum >= X) { ans = i + 1; break; }
    }
    cout << ans << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O(N \log N)$（主要来自排序），扫描部分 $O(N)$
• 空间复杂度：$O(N)$

---

D - Paid Walk

题目链接：https://atcoder.jp/contests/abc441/tasks/abc441_d

题目大意

给定一个 $N$ 个点、$M$ 条边的有向图（可能含重边与自环），第 $i$ 条边从 $U_i$ 指向 $V_i$，代价为 $C_i$。已知每个点的出度至多为 $4$。求所有满足以下条件的顶点 $v$：存在一条从顶点 $1$ 出发、恰好经过 $L$ 条边、且总代价在 $[S, T]$ 之间的路径到达 $v$（同一条边走多次则多次计数）。按升序输出这些顶点；若没有则输出一个空行。

思路

先看数据范围：$L \le 10$，每个点出度 $\le 4$。这说明从顶点 $1$ 出发、恰好走 $L$ 条边的路径总数非常有限，可以暴力枚举。

路径数上界的证明（归纳法）：记 $P_k$ 为从 $1$ 出发恰好走 $k$ 条边的路径数。$k=1$ 时，只能从 $1$ 出发，至多走出度条数 $4$ 条，即 $P_1 \le 4$。假设 $P_k \le 4^k$，那么 $k+1$ 条边的路径可以看作在一条 $k$ 条边的路径末尾再走一条边，而最后那个顶点的出度至多 $4$，故 $P_{k+1} \le 4^k \times 4 = 4^{k+1}$。因此 $P_L \le 4^L \le 4^{10} = 1048576$，完全可以接受。

算法：DFS 枚举所有路径。DFS 状态为（当前顶点 $v$，已走边数 $d$，累计代价 $cost$）：

• 若 $d = L$：检查 $S \le cost \le T$ 是否成立，成立则把顶点 $v$ 标记为可行，返回；
• 若 $d < L$：枚举 $v$ 的每条出边 $(to, c)$，递归进入 $(to, d+1, cost+c)$。

由于同一个顶点可能被多条路径到达，用布尔数组记录"是否存在合法路径到达"，最后把所有标记为真的顶点按编号升序输出。

边界与易错点：

• 图可能有自环和重边，处理时全部保留即可，DFS 自然处理；
• 代价上限为 $L \times C_i \le 10 \times 10^8 = 10^9$，用 64 位整数累计更稳妥；
• 注意顶点 $1$ 本身也可能满足条件（如样例 1 中 $1 \to 2 \to 5 \to 1$ 恰好 $L=3$ 条边回到 $1$）；
• 没有可行顶点时也要输出一个空行。

（可选优化：因为所有边代价为正，一旦 $cost > T$ 即可剪枝，不过题目范围内不剪枝也足够快。）

参考代码

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

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

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

    vector<vector<pair<int, int>>> g(N); // (to, cost)
    for (int i = 0; i < M; ++i) {
        int u, v, c;
        cin >> u >> v >> c;
        --u; --v;
        g[u].push_back({v, c});
    }

    vector<bool> ok(N, false);
    function<void(int, int, ll)> dfs = [&](int v, int d, ll cost) {
        if (d == L) {
            if (S <= cost && cost <= T) ok[v] = true;
            return;
        }
        for (auto [to, c] : g[v]) {
            if (cost + c > T) continue; // 剪枝（可选）
            dfs(to, d + 1, cost + c);
        }
    };
    dfs(0, 0, 0);

    bool first = true;
    for (int i = 0; i < N; ++i) {
        if (ok[i]) {
            if (!first) cout << ' ';
            first = false;
            cout << i + 1;
        }
    }
    cout << '\n';
    return 0;
}

复杂度分析

• 时间复杂度：$O(4^L)$（DFS 枚举的路径总数上界），约 $10^6$ 量级
• 空间复杂度：$O(N + M)$（存图），递归栈深度为 $O(L)$

---

E - A > B substring

题目链接：https://atcoder.jp/contests/abc441/tasks/abc441_e

题目大意

给定一个长度为 $N$、只含 A、B、C 三种字符的字符串 $S$。$S$ 一共有 $\frac{N(N+1)}2$ 个非空连续子串，统计其中 A 的个数严格多于 B 的个数的子串数量。注意：取自不同位置的子串即使内容相同也要分别计数。

思路

关键转化：把"区间内 A、B 的个数比较"转成前缀差的比较。

设 $A_i$、$B_i$ 分别表示 $S$ 前 $i$ 个字符中 A 和 B 的个数，定义

$$D_i = A_i - B_i \quad (0 \le i \le N),\qquad D_0 = 0 .$$

子串 $S[i..j]$（$1 \le i \le j \le N$）中 A 的个数多于 B 的个数，即

$$A_j - A_{i-1} > B_j - B_{i-1} \quad\Longleftrightarrow\quad A_j - B_j > A_{i-1} - B_{i-1} \quad\Longleftrightarrow\quad D_j > D_{i-1} .$$

于是问题等价于：在序列 $D_0, D_1, \ldots, D_N$ 中统计满足 $i < j$ 且 $D_i < D_j$ 的有序对 $(i,j)$ 的个数（这里 $i$ 扮演原式中的 $i-1$）。注意 C 字符不改变 $A_i - B_i$，因此它对 $D$ 序列没有任何影响——这是题目故意放的干扰项。

做法一（树状数组 / Fenwick）：从 $j = 0$ 到 $N$ 扫描，每遇到一个 $j$，先查询"之前出现过的 $D_i$ 中小于 $D_j$ 的个数"并累加，再把 $D_j$ 插入。因为 $D_i \in [-N, N]$，给下标加偏移量 $N$ 后即可作为树状数组下标。时间复杂度 $O(N \log N)$。

做法二（线性扫描，官方题解做法）：既然只关心"小于某值的个数"，可以维护：

• $cnt[d]$：到目前为止 $D_j = d$ 的下标个数；
• $sum = \sum_{d < D_{\text{当前}}} cnt[d]$，即当前前缀 $D$ 之前所有比它小的个数。

扫描到每个字符时：

• 读到 A：$D$ 从 $d$ 变到 $d+1$。"$< d+1$ 的个数"比"$< d$ 的个数"恰好多出 $cnt[d]$，所以先 $sum \mathrel{+}= cnt[d]$，再 $D$ 自增；
• 读到 B：$D$ 从 $d$ 变到 $d-1$。"$< d-1$ 的个数"比"$< d$ 的个数"少了 $cnt[d-1]$，所以先 $D$ 自减，再 $sum \mathrel{-}= cnt[d]$（此时 $d$ 已为 $d-1$）；
• 读到 C：$D$ 与 $sum$ 都不变。

处理完新的 $D$ 之后，先把 $sum$ 累加到答案（$sum$ 就是以当前下标为右端点 $j$ 的合法子串数），再把当前 $D$ 计入 $cnt$。

正确性：$D$ 值只会 $\pm 1$ 地连续变化，因此这种"增量维护 $sum$"的方式能时刻保持 $sum = \sum_{d < D} cnt[d]$。

注意：答案最多有 $\frac{N(N+1)}2 \approx 1.25\times 10^{11}$ 个（$N = 5\times 10^5$），必须用 64 位整数存储。

参考代码

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

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

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

    // D 的取值范围为 [-N, N]，加偏移量 N 映射到 [0, 2N]
    vector<int> cnt(2 * N + 1, 0);
    int d = N;         // 当前前缀差 D_i（已加偏移量），初始 D_0 = 0
    cnt[d] = 1;        // D_0 = 0 出现一次
    ll sum = 0;        // 之前所有 D_j < 当前 D 的个数
    ll ans = 0;

    for (char c : S) {
        if (c == 'A') {
            sum += cnt[d];   // D: d -> d+1，新增的小于 d+1 的是原来等于 d 的
            ++d;
        } else if (c == 'B') {
            --d;             // D: d -> d-1，需要去掉原来等于 d-1 的
            sum -= cnt[d];
        }
        // c == 'C'：D 与 sum 不变

        ++cnt[d];            // 记录当前前缀的 D 值
        ans += sum;          // 以当前位置为右端点的合法子串数
    }

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

复杂度分析

• 时间复杂度：$O(N)$（线性做法；用树状数组则为 $O(N \log N)$）
• 空间复杂度：$O(N)$（长度为 $2N+1$ 的计数数组）

---

F - Must Buy

题目链接：https://atcoder.jp/contests/abc441/tasks/abc441_f

题目大意

商店里有 $N$ 件商品，第 $i$ 件价格 $P_i$、价值 $V_i$，每种只有一件。Takahashi 选择若干件使得总价不超过 $M$，并希望总价值最大。题目保证 $M \ge P_i$ 对每个 $i$ 都成立（即每件商品都单独买得起）。对每件商品 $i$，判断它属于哪一类：

• 类别 A：要使总价值最大，该商品必须被选；
• 类别 B：要使总价值最大，该商品可选可不选；
• 类别 C：要使总价值最大，该商品必不能选。

输出一个长度为 $N$ 的字符串。

思路

这是 0/1 背包问题的变种，核心想法是：把"是否属于某个最优解"拆成两个不含该商品的子问题来判断。

先做标准的 0/1 背包 DP。定义

$$dp[i][j] = \text{从前 } i \text{ 件商品中选、总价不超过 } j \text{ 的最大价值},$$

转移为 $dp[i][j] = \max(dp[i-1][j],\ dp[i-1][j-P_i] + V_i)$（$j < P_i$ 时只能不选）。整体最大价值 $X = dp[N][M]$。

再定义后缀 DP

$$dp2[i][j] = \text{从第 } i \text{ 件到第 } N \text{ 件中选、总价不超过 } j \text{ 的最大价值},$$

用相同的方法从后往前递推。

对每件商品 $i$，判断两个条件：

1. 不用商品 $i$ 能否达到 $X$？ 把总预算 $M$ 拆成两部分 $j$ 和 $M-j$，分别交给前 $i-1$ 件和后 $i+1$ 件，则"不含 $i$ 能凑出的最大价值"为

   $$mx_{\text{woi}} = \max_{0 \le j \le M} \Big( dp[i-1][j] + dp2[i+1][M-j] \Big).$$

   若 $mx_{\text{woi}} = X$，说明存在不选 $i$ 的最优方案。

2. 选商品 $i$ 能否达到 $X$？ 商品 $i$ 占掉价格 $P_i$、提供价值 $V_i$，其余商品共用预算 $M-P_i$，需要凑出价值 $X - V_i$：

   $$mx_{\text{wi}} = \max_{0 \le j \le M-P_i} \Big( dp[i-1][j] + dp2[i+1][M-P_i-j] \Big).$$

   若 $mx_{\text{wi}} = X - V_i$，说明存在选 $i$ 的最优方案。

分类规则：

条件 1（不含 $i$ 达 $X$）	条件 2（含 $i$ 达 $X$）	类别	含义
否	是	A	每个最优解都必须含 $i$
是	是	B	最优解中可选可不选 $i$
是	否	C	任何最优解都不含 $i$

注意两个条件不可能同时为否：否则既不存在含 $i$ 的最优解、也不存在不含 $i$ 的最优解，与"$X$ 可由某个方案达到"矛盾。因此用 if (mx_woi < X) 'A'、else if (mx_wi < X - V_i) 'C'、else 'B' 即可正确判定。

复杂度：两张 DP 表各 $O(NM)$ 时间。$N = 1000, M = 5\times 10^4$ 时 $NM = 5\times 10^7$，若按官方题解存两张完整的 $1001 \times 50001$ 的 64 位表，约需 $2 \times 1001 \times 50001 \times 8 \approx 800$ MB（仍在 ABC 常见的 1024 MB 内存限制内）。参考代码做了优化：正向表 $dp$ 完整存储，反向只滚动维护一行（因为从 $i = N$ 到 $1$ 反向处理商品时，后缀 DP 每次只需要"第 $i+1$ 行"），内存可降到约 400 MB。

参考代码

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

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

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

    // dp[i][j]: 用商品 [0, i)（前 i 件），总价不超过 j 的最大价值
    vector<vector<ll>> dp(N + 1, vector<ll>(M + 1, 0));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j <= M; ++j) {
            dp[i + 1][j] = dp[i][j];
            if (j >= P[i]) dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - P[i]] + V[i]);
        }
    }
    ll X = dp[N][M]; // 全局最大价值

    // suff[j]: 当前已经处理的"右侧商品"中，总价不超过 j 的最大价值
    // 处理到商品 i 时，suff 表示商品 [i+1, N) 的后缀 DP 行
    vector<ll> suff(M + 1, 0);

    string ans(N, '?');
    for (int i = N - 1; i >= 0; --i) {
        // 条件 1：不含商品 i 能否达到 X
        ll mx_woi = 0;
        for (int j = 0; j <= M; ++j)
            mx_woi = max(mx_woi, dp[i][j] + suff[M - j]);

        // 条件 2：含商品 i 能否达到 X（其余商品预算 M - P[i]）
        ll mx_wi = 0;
        for (int j = 0; j + P[i] <= M; ++j)
            mx_wi = max(mx_wi, dp[i][j] + suff[M - P[i] - j]);

        if (mx_woi < X) ans[i] = 'A';
        else if (mx_wi < X - V[i]) ans[i] = 'C';
        else ans[i] = 'B';

        // 把商品 i 加入后缀，供下一轮（i-1）使用
        for (int j = M; j >= P[i]; --j)
            suff[j] = max(suff[j], suff[j - P[i]] + V[i]);
    }

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

复杂度分析

• 时间复杂度：$O(NM)$（两张 DP 各 $O(NM)$，每件商品的判定 $O(M)$）
• 空间复杂度：$O(NM)$（参考代码只需一张完整 $dp$ 表 + 一行后缀，约 $1001 \times 50001 \times 8 \approx 400$ MB；官方题解存两张完整表约 800 MB）

---

G - Takoyaki and Flip

题目链接：https://atcoder.jp/contests/abc441/tasks/abc441_g

题目大意

$N$ 个盘子排成一排，初始全部正面朝上且没有章鱼烧。处理 $Q$ 个操作：

• 类型 1（1 L R X）：对区间 $[L,R]$ 中正面朝上的盘子，每个放上 $X$ 个章鱼烧；
• 类型 2（2 L R）：对区间 $[L,R]$ 中每个盘子：若盘子上有章鱼烧，先把章鱼烧全部吃掉，然后翻转盘子（正面↔反面）；
• 类型 3（3 L R）：询问区间 $[L,R]$ 中单个盘子上章鱼烧数量的最大值。

保证至少有一个类型 3 操作。$N, Q \le 2\times 10^5$，答案可能超过 $2^{32}$。

思路

这是区间翻转 + 区间"条件加" + 区间最大值问题，正解是懒标记线段树。难点在于操作 2 会把区间内所有章鱼烧清零并翻转，如何把一段区间上的操作合并成一个惰性标记。

关键观察 1：反面盘子上永远没有章鱼烧。 类型 1 只给正面盘子加章鱼烧；类型 2 先吃掉该盘子上的章鱼烧再翻转。因此任何盘子被翻成反面时，其上的章鱼烧都已被清空，之后它处于反面时也不会收到类型 1 的加成。于是反面盘子的章鱼烧数恒为 $0$，并且类型 2 对任何盘子的效果都是"章鱼烧清零 + 翻转"（正面盘子本来就该先吃再翻，反面盘子本来就没有，吃了也无所谓）。

关键观察 2：一段区间上的操作序列可归约为"先翻 $a$ 次、再加 $b$"。 因为最后一次翻转会把之前所有加法全部清空，所以任意一串操作都等价于：前面若干次翻转（次数记为 $a$，其实只有"是否为 0"和"奇偶"有意义），紧接着若干次加法（总量记为 $b$，只作用于翻转后处于正面的盘子）。用二元组 $(a,b)$ 表示。

关键观察 3：节点信息与施加标记的公式。 每个线段树节点存三元组

$$(mx,\ up,\ down) = \text{(段内最大值, 正面盘子数, 反面盘子数)} .$$

合并两个子节点时 $mx$ 取两者较大者，$up = up_l + up_r$，$down = down_l + down_r$。

对一个段施加标记 $(a,b)$（先翻 $a$ 次，再加 $b$）：

• $a$ 为偶数：朝向不变，加法作用于原本正面的盘子。若 $up > 0$，则 $mx \leftarrow mx + b$；否则段内全为反面，$mx = 0$；
• $a$ 为奇数：朝向互换，加法作用于原本反面、翻转后正面的盘子。由于每次翻转都会清零，此时段内最大值只可能来自刚加的 $b$：若 $down > 0$，则 $mx \leftarrow b$；否则 $mx = 0$；
• $up,\ down$ 相应交换或不交换。

关键观察 4：标记的合并。 先施加 $(a_1,b_1)$，再施加 $(a_2,b_2)$：

$$(a_1,b_1)\oplus(a_2,b_2) = \begin{cases} (a_1,\ b_1 + b_2), & a_2 = 0,\\[2mm] (a_1 + a_2,\ b_2), & a_2 \neq 0 . \end{cases}$$

解释：若第二次操作没有翻转（$a_2=0$），只是再追加 $b_2$ 次加法（加在同一批正面上），所以 $b_1 + b_2$；若第二次操作有翻转（$a_2 \neq 0$），则第一次的所有加法 $b_1$ 都会被第二次的翻转清空，只剩下 $b_2$，翻转次数累加为 $a_1 + a_2$。

操作映射：类型 1 施加标记 $(0, X)$；类型 2 施加标记 $(1, 0)$；类型 3 是区间查询，返回节点信息后取 $mx$。

初始化：每个盘子正面、章鱼烧为 $0$，叶子节点为 $(0, 1, 0)$。之后用标准的递归懒标记线段树实现区间施加标记、区间查询即可。

正确性：以上归约精确刻画了三种操作在"段"层面的语义，且标记合并满足结合律，因此懒标记线段树的正确性成立。

参考代码

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

struct Node {
    ll mx;      // 段内章鱼烧最大值
    int up;     // 正面盘子数
    int down;   // 反面盘子数
};

struct Tag {
    int flip;   // 翻转次数
    ll add;     // 加法总量
};

int N, Q;
vector<Node> seg;
vector<Tag> lazy;

Node mergeNode(const Node& a, const Node& b) {
    return {max(a.mx, b.mx), a.up + b.up, a.down + b.down};
}

// 把标记 t（先翻 t.flip 次，再加 t.add）作用到节点 v 上
Node applyTag(const Tag& t, const Node& v) {
    bool odd = (t.flip & 1);
    int up = odd ? v.down : v.up;      // 翻转后正面盘子数
    int down = odd ? v.up : v.down;    // 翻转后反面盘子数
    ll mx;
    if (up == 0) {
        mx = 0;
    } else if (t.flip > 0) {
        mx = t.add;                    // 有翻转：段内被清零后只加了 add
    } else {
        mx = v.mx + t.add;             // 无翻转：正面盘子整体 +add
    }
    return {mx, up, down};
}

// 合并标记：先施加 first，再施加 second
Tag mergeTag(const Tag& first, const Tag& second) {
    if (second.flip == 0) return {first.flip, first.add + second.add};
    return {first.flip + second.flip, second.add};
}

void build(int node, int l, int r) {
    lazy[node] = {0, 0};
    if (l == r) {
        seg[node] = {0, 1, 0};         // 初始：正面、0 个章鱼烧
        return;
    }
    int mid = (l + r) / 2;
    build(node * 2, l, mid);
    build(node * 2 + 1, mid + 1, r);
    seg[node] = mergeNode(seg[node * 2], seg[node * 2 + 1]);
}

void push(int node) {
    if (lazy[node].flip == 0 && lazy[node].add == 0) return;
    seg[node * 2] = applyTag(lazy[node], seg[node * 2]);
    lazy[node * 2] = mergeTag(lazy[node * 2], lazy[node]);
    seg[node * 2 + 1] = applyTag(lazy[node], seg[node * 2 + 1]);
    lazy[node * 2 + 1] = mergeTag(lazy[node * 2 + 1], lazy[node]);
    lazy[node] = {0, 0};
}

void apply(int node, int l, int r, int ql, int qr, const Tag& t) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
        seg[node] = applyTag(t, seg[node]);
        lazy[node] = mergeTag(lazy[node], t);
        return;
    }
    push(node);
    int mid = (l + r) / 2;
    apply(node * 2, l, mid, ql, qr, t);
    apply(node * 2 + 1, mid + 1, r, ql, qr, t);
    seg[node] = mergeNode(seg[node * 2], seg[node * 2 + 1]);
}

Node query(int node, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return {0, 0, 0};  // 恒等元：mx 取较大者时不影响
    if (ql <= l && r <= qr) return seg[node];
    push(node);
    int mid = (l + r) / 2;
    return mergeNode(query(node * 2, l, mid, ql, qr),
                     query(node * 2 + 1, mid + 1, r, ql, qr));
}

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

    cin >> N >> Q;
    seg.resize(4 * N);
    lazy.resize(4 * N);
    build(1, 1, N);

    while (Q--) {
        int t, L, R;
        cin >> t >> L >> R;
        if (t == 1) {
            ll X;
            cin >> X;
            apply(1, 1, N, L, R, {0, X});   // 加章鱼烧（只加在正面上）
        } else if (t == 2) {
            apply(1, 1, N, L, R, {1, 0});   // 清空并翻转
        } else {
            cout << query(1, 1, N, L, R).mx << '\n';
        }
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O((N + Q)\log N)$（建树 $O(N)$，每个区间操作 $O(\log N)$）
• 空间复杂度：$O(N)$（线段树数组）