AtCoder Beginner Contest 430 题解

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

比赛概览

本场整体难度前低后高：A 是简单条件判断，B 是暴力枚举 + set 去重；C 是经典"前缀和 + 单调双指针"的区间计数；D 的亮点在于"差分更新"（每次插入只重算受影响的 $O(1)$ 个点）；E 用 Z 算法判断字符串循环移位；F 需要推导出"每个整数可放置的格子构成一个连续区间"这一关键定理；G 则是一道较有区分度的 Segment Tree Beats 题。建议重点掌握 C 的双指针思想、D 的差分更新、F 的连续区间定理，以及 G 的"当节点信息无法直接整体更新时下推递归再上拉"的核心套路。

---

A - Candy Cookie Law

题目链接：https://atcoder.jp/contests/abc430/tasks/abc430_a

题目大意

AtCoder 国有一条奇怪的法律："拥有 $A$ 个及以上糖果的人，必须拥有 $B$ 个及以上饼干。"高桥拥有 $C$ 个糖果和 $D$ 个饼干，判断他是否违反这条法律。合法时输出 No，违法时输出 Yes。约束：$1\le A,B,C,D\le 100$。

思路

这是一道条件判断题。法律只约束"糖果数 $\ge A$"的情形：此时必须满足"饼干数 $\ge B$"，即 $D\ge B$。

因此违法当且仅当：

$$C \ge A \quad\text{且}\quad D < B.$$

其余情况（$C<A$，或 $D\ge B$）都不违法。例如样例 3 中 $C=1<A=100$，触发不了法律，所以合法。

易错点：注意"糖果不足不触发法律"这一逻辑，不要写成"$C\ge A$ 且 $D\le B$"之类；只有 $D<B$ 才算饼干不足。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    if (C >= A && D < B) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

官方题解给出的 Python 实现：

A, B, C, D = map(int, input().split())
if (C >= A) and (D < B):
    print("Yes")
else:
    print("No")

复杂度分析

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

---

B - Count Subgrid

题目链接：https://atcoder.jp/contests/abc430/tasks/abc430_b

题目大意

有一个 $N$ 行 $N$ 列的网格，第 $i$ 行第 $j$ 列的格子是黑色（#）或白色（.）。从网格中取出一个 $M$ 行 $M$ 列的区域，问能得到的不同涂色图案有多少种。约束：$1\le M\le N\le 10$。

思路

关键观察：$N\le 10$ 非常小。所有可能的 $M\times M$ 区域一共有 $(N-M+1)^2$ 个（由左上角 $(i,j)$ 唯一确定），最多 $9^2=81$ 个；每个区域内部只有 $M^2\le 100$ 个字符。因此直接枚举所有区域，把每个区域的图案整体放入一个 set 去重，最后 set 的大小就是答案。

"统计不同的东西有几个"时，用 set 去重是最直接的做法。具体地：

1. 枚举左上角 $(i,j)$，其中 $0\le i,j\le N-M$。
2. 取出 $S[i..i+M-1]$ 中每一行的第 $j$ 到 $j+M-1$ 列，拼成一个 $M\times M$ 的图案。
3. 插入 set。

易错点：C++ 中 set<vector<string>> 天然支持比较，可直接使用；Python 中 list 不可哈希，需改用元组 tuple。

参考代码

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

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

    set<vector<string>> pat;
    for (int i = 0; i + M <= N; i++) {
        for (int j = 0; j + M <= N; j++) {
            vector<string> sub;
            for (int ii = i; ii < i + M; ii++) sub.push_back(S[ii].substr(j, M));
            pat.insert(sub);
        }
    }
    cout << pat.size() << '\n';
    return 0;
}

官方题解给出的 Python 实现：

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

pat = set()
for i in range(N - M + 1):
    for j in range(N - M + 1):
        sub = tuple(S[ii][j:j + M] for ii in range(i, i + M))
        pat.add(sub)

print(len(pat))

复杂度分析

• 时间复杂度：$O((N-M+1)^2 M^2)$，即 $O(N^2M^2)$（此处 $N\le 10$，非常小）
• 空间复杂度：$O(KM^2)$，其中 $K$ 为不同图案数（至多 $(N-M+1)^2$）

---

C - Truck Driver

题目链接：https://atcoder.jp/contests/abc430/tasks/abc430_c

题目大意

给定长度为 $N$、仅含 a 和 b 的字符串 $S$，以及正整数 $A,B$。求满足以下条件的整数对 $(l,r)$ 的个数：

• $1\le l\le r\le N$；
• 子串 $S[l..r]$ 中 a 的个数 $\ge A$；
• 子串 $S[l..r]$ 中 b 的个数 $< B$。

约束：$1\le N\le 3\times 10^5$。

思路

第一步：前缀和。 设

$$\mathrm{preA}[i]=\#\{k\le i:S_k=\texttt{a}\},\qquad \mathrm{preB}[i]=\#\{k\le i:S_k=\texttt{b}\},$$

则区间 $[l,r]$ 内 a、b 的个数分别为 $\mathrm{preA}[r]-\mathrm{preA}[l-1]$ 和 $\mathrm{preB}[r]-\mathrm{preB}[l-1]$，可 $O(1)$ 求出。

第二步：固定 $l$，看 $r$ 的合法区间。 固定 $l$ 时，$r$ 增大，区间内 a 和 b 的个数都单调不减，所以两条约束分别给出 $r$ 的一个下界和一个上界：

• a 条件：令 $a_l$ 为使区间 $[l,r]$ 内含 $\ge A$ 个 a 的最小 $r$。则 $r\ge a_l$。
• b 条件：令 $b_l$ 为使区间 $[l,r]$ 内含 $<B$（即 $\le B-1$）个 b 的最大 $r$。则 $r\le b_l$。

于是固定 $l$ 的贡献为

$$\max(0,\; b_l-a_l+1).$$

第三步：高效求 $a_l,b_l$。 注意当 $l$ 增大时，$\mathrm{preA}[l-1]$ 不减，所以 $a_l$ 关于 $l$ 单调不减；$\mathrm{preB}[l-1]$ 也不减，所以 $b_l$ 关于 $l$ 单调不减。因此可以用两个只前进不后退的指针 $rA, rB$ 依次扫描，整体 $O(N)$；也可以用二分查找对每个 $l$ 求 $a_l,b_l$，整体 $O(N\log N)$。这里给出 $O(N)$ 的双指针写法。

边界情况与易错点：

1. $a_l$ 可能不存在：若 $\mathrm{preA}[N]-\mathrm{preA}[l-1]<A$，说明从 $l$ 到末尾的 a 总个数都不够。又因该值随 $l$ 增大而递减，此后所有 $l$ 都不可能满足，直接跳出循环。
2. $b$ 条件是"$<B$"，即 $\le B-1$，别忘了 $-1$。
3. 指针 $rB$ 可能小于 $rA$（此时没有合法的 $r$，贡献为 0），但 $rB$ 仍需继续为后续 $l$ 维护；因为 $rB$ 的合法上界单调不减，从当前值继续前进即可。
4. 答案最大约 $O(N^2)$，要用 long long。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N, A, B;
    string S;
    cin >> N >> A >> B >> S;

    vector<int> preA(N + 1, 0), preB(N + 1, 0);
    for (int i = 0; i < N; i++) {
        preA[i + 1] = preA[i] + (S[i] == 'a');
        preB[i + 1] = preB[i] + (S[i] == 'b');
    }

    long long ans = 0;
    int rA = 1, rB = 1;
    for (int l = 1; l <= N; l++) {
        // 剩余 a 的数量不足 A，之后所有 l 都不可能满足
        if (preA[N] - preA[l - 1] < A) break;

        // a_l：使 a 个数 >= A 的最小 r
        while (rA <= N && preA[rA] - preA[l - 1] < A) rA++;

        // b_l：使 b 个数 <= B-1 的最大 r
        while (rB < N && preB[rB + 1] - preB[l - 1] <= B - 1) rB++;

        if (rB >= rA) ans += rB - rA + 1;
    }
    cout << ans << '\n';
    return 0;
}

若想用二分查找，只需把指针推进换成"对每个 $l$ 二分求 $a_l$ 与 $b_l$"，思路完全一致，复杂度变为 $O(N\log N)$。

复杂度分析

• 时间复杂度：$O(N)$（双指针）；二分写法为 $O(N\log N)$
• 空间复杂度：$O(N)$

---

D - Neighbor Distance

题目链接：https://atcoder.jp/contests/abc430/tasks/abc430_d

题目大意

数轴上，初始时只有 person $0$ 站在坐标 $0$。之后 person $1,2,\dots,N$ 依次到达，person $i$ 站在坐标 $X_i$（$X_i\ge 1$，且互不相同）。每当 person $r$ 到达后，当前有 $r+1$ 个人，定义 person $i$ 的"最近距离"

$$d_i=\min_{0\le j\le r,\;j\ne i}|X_i-X_j|,$$

输出 $\sum_{i=0}^{r}d_i$。共输出 $N$ 行。约束：$N\le 5\times 10^5$。

思路

关键观察（差分更新）：一个点 $p$ 的最近距离只由它左右两个邻居决定。当新点 $x$ 插入时，只有以下三类点的邻居关系可能发生变化：

• $x$ 的前驱 $\mathrm{pred}(x)$（原来右边的邻居是 $\mathrm{succ}(x)$，现在变成了 $x$）；
• $x$ 的后继 $\mathrm{succ}(x)$；
• 新点 $x$ 自己。

其余所有点的最近距离都不变。因此我们不需要在每次插入后全量重算，只需维护一个有序集合，并做"减去旧的、加上新的"的局部修正。这种只重算受影响因子的技巧叫做差分更新（differential update），在算法题与启发式比赛中都很常用。

做法（Approach 1）：

1. 用 std::set<int> 维护当前所有坐标（初始包含 $0$）。
2. 维护全局答案 res。
3. 插入新点 $x$ 前，在旧集合中找到前驱、后继，把它们的旧最近距离从 res 中减去。
4. 插入 $x$。
5. 对前驱、$x$、后继分别计算新最近距离，加到 res 上。
6. 输出 res。

其中"最近距离"函数 $\mathrm{nearest}(v)$ 为 $v$ 与前驱、后继的距离的较小值（某一侧不存在则忽略）。

为什么正确：插入 $x$ 后，集合中任意点 $v\notin\{\mathrm{pred}(x),x,\mathrm{succ}(x)\}$ 的左右邻居都不变，故其最近距离不变；只有这三个点的最近距离可能改变。逐一修正即可。

关于 int 的一个有趣的"Bonus"：官方代码用 int 存储答案，看似危险（$N\le 5\times 10^5$，每个距离可达 $10^9$），但实际不会溢出。设当前坐标为 $p_1<p_2<\cdots<p_m$，记 $d_i=p_{i+1}-p_i$，则

$$\sum_i \min(d_{i-1},d_i) \le d_1 + \sum_{i=2}^{m-1}d_{i-1} + d_{m-1} \le 2(p_m-p_1)\le 2\times 10^9,$$

小于 $2^{31}-1\approx 2.147\times 10^9$。即"最近距离总和"不超过跨距的两倍。当然，写题解代码时用 long long 更稳妥。

参考代码

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

int nearest(int x, const set<int>& st) {
    auto it = st.find(x);
    int res = INT_MAX;
    if (it != st.begin()) {          // 有前驱
        auto jt = it;
        --jt;
        res = min(res, x - *jt);
    }
    ++it;
    if (it != st.end()) res = min(res, *it - x);   // 有后继
    return res;
}

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

    int N;
    cin >> N;
    set<int> st;
    long long res = 0;

    int x;
    cin >> x;
    st.insert(0);
    st.insert(x);
    res = 2LL * x;                     // person 0 和 person 1 互为最近
    cout << res << '\n';

    for (int i = 1; i < N; i++) {
        cin >> x;
        vector<int> hit;
        auto it = st.lower_bound(x);
        if (it != st.end()) hit.push_back(*it);   // 后继
        if (it != st.begin()) {
            --it;
            hit.push_back(*it);                   // 前驱
        }
        for (int v : hit) res -= nearest(v, st);  // 减去旧的
        st.insert(x);
        hit.push_back(x);
        for (int v : hit) res += nearest(v, st);  // 加上新的
        cout << res << '\n';
    }
    return 0;
}

（另一种 Approach 2：利用"插入只会使最近距离减小"这一性质，直接对前驱、后继维护"当前最近距离"的最小值，同样 $O(N\log N)$。）

复杂度分析

• 时间复杂度：$O(N\log N)$（每次插入做常数次 set 查找与插入）
• 空间复杂度：$O(N)$

---

E - Shift String

题目链接：https://atcoder.jp/contests/abc430/tasks/abc430_e

题目大意

给定等长的 0/1 字符串 $A$ 和 $B$。每次操作把 $A$ 的第一个字符移到末尾（即循环左移一位）。求最少需要多少次操作才能使 $A=B$；如果无论怎么操作都不可能，输出 $-1$。有 $T$ 组数据，$\sum |A|\le 10^6$。

思路

问题转化：左移 $k$ 次后，$A$ 变成

$$A[k+1..n] + A[1..k],$$

即 $A$ 的"循环左移 $k$ 位"。要求的是满足"循环左移 $k$ 位后等于 $B$"的最小 $k$（$0\le k<n$）。因为左移 $n$ 次回到原串，所以 $k\ge n$ 是多余的。

用 Z 算法判断循环移位：构造字符串

$$S = B + A + A,$$

然后对 $S$ 求 Z 数组。回忆 Z 数组的定义：$z[i]$ 是 $S$ 与 $S[i..]$ 的最长公共前缀长度。

• $S$ 的下标 $0..n-1$ 是 $B$；
• 下标 $n..2n-1$ 是 $A$ 的拷贝，下标 $n+k$ 开始的 $n$ 个字符恰好是 $A$ 循环左移 $k$ 位的结果。

因此对 $k=0,1,\dots,n-1$：

$$z[n+k] \ge n \iff A\text{ 循环左移 }k\text{ 位 }= B.$$

从 $k=0$ 起从小到大检查，第一个满足的 $k$ 就是最小操作次数；全部不满足则输出 $-1$。

Z 算法可以在 $O(|S|)$ 时间内求出整个 Z 数组（维护当前最右的匹配区间 $[l,r)$）。总长度 $\sum 3n \le 3\times 10^6$，完全可行。

易错点：下标 $n+k$ 不要写成别的偏移；判断条件是 $\ge n$ 而不是 $> n$；找到就立刻输出（保证最小 $k$）。

参考代码

#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;
    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i < r) z[i] = min(r - i, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++;
        if (i + z[i] > r) {
            l = i;
            r = i + z[i];
        }
    }
    return z;
}

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

    int T;
    cin >> T;
    while (T--) {
        string A, B;
        cin >> A >> B;
        int n = (int)A.size();
        string S = B + A + A;
        vector<int> z = z_algorithm(S);

        int ans = -1;
        for (int k = 0; k < n; k++) {
            if (z[n + k] >= n) {
                ans = k;
                break;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

复杂度分析

• 时间复杂度：每组 $O(n)$（Z 算法线性），总计 $O(\sum |A|)$
• 空间复杂度：$O(n)$（Z 数组与 $S$）

---

F - Back and Forth Filling

题目链接：https://atcoder.jp/contests/abc430/tasks/abc430_f

题目大意

有 $N$ 个格子排成一行，要把整数 $1,2,\dots,N$ 各写进恰好一个格子。给定长度为 $N-1$ 的字符串 $S$：若 $S[i]=\texttt{L}$，要求 $i+1$ 写在 $i$ 的左边；若 $S[i]=\texttt{R}$，要求 $i+1$ 写在 $i$ 的右边。设 $C_i$ 为"能写在第 $i$ 个格子里的不同整数的个数"，输出 $C_1,\dots,C_N$。有 $T$ 组数据，$\sum N\le 3\times 10^5$。

思路

关键定理：对每个整数 $v$，$v$ 能出现的格子构成一个连续区间 $[l_v,r_v]$。求出所有区间的左右端点后，用差分数组累加即可得到每个格子的 $C_i$。下面推导 $l_v,r_v$。

先把约束写成偏序：$S[i]=\texttt{L}\Rightarrow i+1$ 在 $i$ 左侧；$S[i]=\texttt{R}\Rightarrow i$ 在 $i+1$ 左侧。定义四个"最长连续段"长度（字符串按 $1..N-1$ 编号）：

• $p$：以 $S[v-1]$ 结尾的最长 $\texttt{R}$ 段长度（若 $v=1$ 则为 $0$）；
• $q$：以 $S[v]$ 开头的最长 $\texttt{L}$ 段长度（若 $v=N$ 则为 $0$）；
• $p'$：以 $S[v-1]$ 结尾的最长 $\texttt{L}$ 段长度；
• $q'$：以 $S[v]$ 开头的最长 $\texttt{R}$ 段长度。

则 $v$ 的可行格子（0 基下标）为

$$\boxed{\ [\,p+q,\ \ N-1-p'-q'\,]\ }.$$

为什么 $v$ 左侧至少有 $p+q$ 个元素（下界）：

• 若 $S[v-1]=\texttt{R}$，则 $v$ 在 $v-1$ 右侧。设以 $S[v-1]$ 结尾的最长 $\texttt{R}$ 段为 $S[v-p],\dots,S[v-1]$，链式推出

  $$v-p < v-p+1 < \cdots < v-1 < v,$$

  这 $p$ 个数都必须位于 $v$ 左侧。
• 若 $S[v]=\texttt{L}$，则 $v+1$ 在 $v$ 左侧。$\texttt{L}$ 段 $S[v],\dots,S[v+q-1]$ 链式推出

  $$v+q < \cdots < v+1 < v,$$

  这 $q$ 个数都必须位于 $v$ 左侧。

对称地，以 $S[v-1]$ 结尾的 $\texttt{L}$ 段（长度 $p'$）与以 $S[v]$ 开头的 $\texttt{R}$ 段（长度 $q'$）所涉及的元素（分别是 $v-p',\dots,v-1$ 与 $v+1,\dots,v+q'$）必须位于 $v$ 右侧。因此 $v$ 的格子至少为 $p+q$、至多为 $N-1-p'-q'$。

为什么中间的每个格子都能达到（充分性）：除上述必须位于左侧/右侧的元素外，其余元素与 $v$ 之间不存在"决定性"约束——它们之间的相邻字符链中至少有一处"转向"，因此可以自由分布在 $v$ 的两侧。更严格地：设 $v$ 左侧那段最长段在字符 $\alpha$ 处停下、右侧段在字符 $\beta$ 处停下，把整数分为 $A=\{1,\dots,\alpha\}$、$B=\{\alpha+1,\dots,\beta\}$（含 $v$）、$C=\{\beta+1,\dots,N\}$ 三块。每块内部的相对顺序分别由块内约束确定，而跨块的约束只有 $S[\alpha]$ 与 $S[\beta]$；恰好因为这两处是"转向点"（与相邻段的字母相反），$A$ 块与 $C$ 块可以按各自内部顺序自由地插入 $B$ 的任意空隙，特别是可以把任意个数的 $A/C$ 元素放在 $v$ 的左侧、其余放在右侧。于是 $v$ 的格子可连续地从 $p+q$ 一直取到 $N-1-p'-q'$。

例：$S=\texttt{LRRLLLR}$，求 $4$ 能放的位置。$S[3]=\texttt{R}$ 且 $S[2]=\texttt{R}$，故 $2<3<4$，$2,3$ 必须位于 $4$ 左侧；$S[4..6]=\texttt{LLL}$ 链式推出 $7<6<5<4$，$5,6,7$ 也必须在 $4$ 左侧。共 $5$ 个元素在左侧，因此 $4$ 最左可到第 $6$ 格；而 $1,8$ 均可自由选择左右，于是 $4$ 可取第 $6,7,8$ 格，与公式吻合。

实现：预处理四个数组（$lp,rp$：以 $i$ 结尾的最长 $\texttt{L/R}$ 段；$ls,rs$：以 $i$ 开头的最长 $\texttt{L/R}$ 段），再对每个 $v$ 计算 $l_v,r_v$，用差分数组 $bk[l]++,bk[r+1]--$ 统计，最后前缀和输出。注意下标：$v$ 的左边相邻字符是 $S[v-1]$，右边是 $S[v]$；代码中统一用 0 基格子下标。

参考代码

#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;
        string S;
        cin >> N >> S;                       // S 长 N-1，按 1..N-1 编号

        vector<int> lp(N + 1, 0), rp(N + 1, 0), ls(N + 1, 0), rs(N + 1, 0);
        // lp[i] / rp[i]：以字符 i 结尾的最长 L / R 段长度
        for (int i = 1; i < N; i++) {
            if (S[i - 1] == 'L') lp[i] = lp[i - 1] + 1;
            else rp[i] = rp[i - 1] + 1;
        }
        // ls[i] / rs[i]：以字符 i 开头的最长 L / R 段长度
        for (int i = N - 1; i >= 1; i--) {
            if (S[i - 1] == 'L') ls[i] = ls[i + 1] + 1;
            else rs[i] = rs[i + 1] + 1;
        }

        vector<int> diff(N + 1, 0);
        for (int v = 1; v <= N; v++) {
            int l = rp[v - 1] + ls[v];                 // 必须位于 v 左侧的元素数
            int r = (N - 1) - lp[v - 1] - rs[v];       // N-1 - 必须位于 v 右侧的元素数
            diff[l]++;
            diff[r + 1]--;
        }

        int cur = 0;
        for (int i = 0; i < N; i++) {
            cur += diff[i];
            if (i) cout << ' ';
            cout << cur;
        }
        cout << '\n';
    }
    return 0;
}

复杂度分析

• 时间复杂度：每组 $O(N)$
• 空间复杂度：每组 $O(N)$

---

G - Range Set Modifying Query

题目链接：https://atcoder.jp/contests/abc430/tasks/abc430_g

题目大意

有 $N$ 个集合 $S_1,\dots,S_N$，初始均为空。处理 $Q$ 个查询：

• 1 L R x：对 $[L,R]$ 中每个集合加入 $x$；
• 2 L R x：对 $[L,R]$ 中每个集合删除 $x$；
• 3 L R：输出 $[L,R]$ 内集合大小的最大值，以及达到该最大值的集合个数。

约束：$N,Q\le 3\times 10^5$，$1\le x\le 60$。

思路

难点：区间加一个元素并不是对"大小数组"做区间加——区间内有些集合已含 $x$（大小不变），有些不含（大小 $+1$）。朴素懒标记线段树无法在 $O(\log N)$ 内完成这样的更新。

Segment Tree Beats 解法（官方）。核心思想：如果"整块更新"所需的信息无法仅由节点本身直接算出，就把懒标记下推、递归处理子节点，再自底向上重新合并；只要这种情况出现得不频繁，总复杂度就有保证。

每个节点维护：

• $O$：区间内所有集合的并集（用 $60$ 位位掩码表示）；
• $A$：区间内所有集合的交集；
• $\mathrm{mx}$：区间内集合大小的最大值；
• $\mathrm{cnt}$：达到 $\mathrm{mx}$ 的集合个数。

懒标记表示映射 $f(x)=(x\setminus a)\cup b$，在代码里写成保留掩码与新增掩码：

$$f(x)=(x\cap \mathrm{keep})\cup \mathrm{add}.$$

• 加入 $x$：$\mathrm{keep}=$ 全 1，$\mathrm{add}=\{x\}$；
• 删除 $x$：$\mathrm{keep}=$ 全 1 $\setminus\{x\}$，$\mathrm{add}=\varnothing$。

映射成功的条件：当

$$(O\setminus A)\cap(\text{删除}\cup\text{新增})=\varnothing$$

时，所有被修改的元素在该区间内要么全部存在、要么全部不存在（是"一致的"），于是可以 $O(1)$ 整块更新：

• 大小变化量 $=$ $-\mathrm{popcount}(A\cap\text{删除})+\mathrm{popcount}((\text{全集}\setminus O)\cap\text{新增})$；
• 再更新 $A,O$ 掩码。

直观地说，就是"从每个集合都有的元素里删去的个数"与"从任何集合都没有的元素里新增的个数"。若条件不满足，则映射失败，执行：

push(k);                      // 把 k 的旧懒标记下推给子节点
all_apply(2k, f); all_apply(2k+1, f);   // 递归地对子节点应用 f
update(k);                    // 由子节点重新合并出 k

这正是 Segment Tree Beats 的关键步骤——失败的节点不再"挂着"懒标记，而是把操作真正下推到能处理的深度，再上拉合并。

复杂度（摊还）：每次映射失败，该节点上 $|O\setminus A|$ 严格减小（被触碰的不一致元素在递归中都被解析为一致）；而一次查询只会让 $O(\log N)$ 个节点的 $|O\setminus A|$ 至多增加 1，且元素总数不超过 $N\cdot \max x\le 60N$。因此映射失败总次数为 $O((N+Q)\log N + N\max x)$，总复杂度 $O((N+Q)\log N+N\max x)$。

（替代解法，无 Segment Tree Beats）：准备 $60$ 棵支持"区间赋值 $0/1$"与"区间内 find_first"的懒标记线段树（第 $x$ 棵记录 $x$ 是否在 $S_i$ 中），再加一棵支持"区间加、区间最大 + 计数"的大小线段树。对一次类型 1/2 查询，只在真正发生变化的最大连续段上做赋值并同步对大小树做区间加。由于相邻位置值不同的"边界"总数有限，真正被操作的段数摊还为 $O(N\max x+Q)$，总复杂度 $O((N\max x+Q)\log N)$。这里给出官方的 Segment Tree Beats 实现。

易错点：掩码只用低 $60$ 位；ALL = (1ULL<<60)-1；~keep 会把高位置 1，但并集/交集的位掩码高位为 0，所以判定条件 $(O\oplus A)\,\&\,(\sim\mathrm{keep}\mid\mathrm{add})$ 不会误判；叶子节点上 $O=A$（单元素集合），映射永远不会失败，递归必然终止。

参考代码

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

using ull = unsigned long long;

const ull ALL = (1ULL << 60) - 1;   // 只使用低 60 位

struct Node {
    ull O, A;      // 并集、交集（60 位掩码）
    int mx, cnt;   // 最大大小、达到最大值的集合个数
};

struct F {
    ull keep, add; // f(x) = (x & keep) | add
};

Node mergeNode(const Node& x, const Node& y) {
    Node r;
    r.O = x.O | y.O;
    r.A = x.A & y.A;
    if (x.mx > y.mx) { r.mx = x.mx; r.cnt = x.cnt; }
    else if (x.mx < y.mx) { r.mx = y.mx; r.cnt = y.cnt; }
    else { r.mx = x.mx; r.cnt = x.cnt + y.cnt; }
    return r;
}

// 尝试整块应用 f；成功返回 true，否则返回 false（需下推递归）
bool applyNode(Node& x, const F& f) {
    ull nonUniform = x.O ^ x.A;          // 区间内"不一致"的元素（A 是 O 的子集）
    if (nonUniform & ((~f.keep) | f.add)) return false;   // 有不一致的元素被修改
    x.mx -= __builtin_popcountll(x.A & ~f.keep);          // 每个集合都有的元素被删
    x.A &= f.keep;
    x.O &= f.keep;
    x.mx += __builtin_popcountll((~x.O) & f.add);         // 任何集合都没有的元素被加
    x.A |= f.add;
    x.O |= f.add;
    return true;
}

F composeF(const F& g, const F& f) {     // 先应用 f，再应用 g
    F r;
    r.keep = f.keep & g.keep;
    r.add = (f.add & g.keep) | g.add;
    return r;
}

bool isId(const F& f) { return f.keep == ALL && f.add == 0; }

struct Beats {
    int n;
    vector<Node> d;
    vector<F> lz;

    Beats(int N) {
        n = 1;
        while (n < N) n <<= 1;
        d.assign(2 * n, {0ULL, ALL, 0, 0});   // 虚节点/空区间：交为全 1
        lz.assign(2 * n, {ALL, 0});
        for (int i = 0; i < N; i++) d[n + i] = {0ULL, 0ULL, 0, 1};  // 空集合
        for (int i = n - 1; i >= 1; i--) d[i] = mergeNode(d[2 * i], d[2 * i + 1]);
    }

    void update(int k) { d[k] = mergeNode(d[2 * k], d[2 * k + 1]); }

    void all_apply(int k, const F& f) {
        if (applyNode(d[k], f)) {
            if (k < n) lz[k] = composeF(f, lz[k]);
        } else {
            push(k);                        // 下推旧懒标记
            all_apply(2 * k, f);            // 递归处理子节点
            all_apply(2 * k + 1, f);
            update(k);                      // 重新合并
        }
    }

    void push(int k) {
        if (isId(lz[k])) return;
        all_apply(2 * k, lz[k]);
        all_apply(2 * k + 1, lz[k]);
        lz[k] = {ALL, 0};
    }

    void range_apply(int L, int R, const F& f) { range_apply(1, 0, n, L, R, f); }
    void range_apply(int k, int l, int r, int L, int R, const F& f) {
        if (R <= l || r <= L) return;
        if (L <= l && r <= R) { all_apply(k, f); return; }
        push(k);
        int m = (l + r) / 2;
        range_apply(2 * k, l, m, L, R, f);
        range_apply(2 * k + 1, m, r, L, R, f);
        update(k);
    }

    Node range_query(int L, int R) { return range_query(1, 0, n, L, R); }
    Node range_query(int k, int l, int r, int L, int R) {
        if (R <= l || r <= L) return {0ULL, ALL, 0, 0};
        if (L <= l && r <= R) return d[k];
        push(k);
        int m = (l + r) / 2;
        return mergeNode(range_query(2 * k, l, m, L, R),
                         range_query(2 * k + 1, m, r, L, R));
    }
};

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

    int N, Q;
    cin >> N >> Q;
    Beats seg(N);

    while (Q--) {
        int t, L, R;
        cin >> t >> L >> R;
        --L;                                // 转成 0 基半开区间 [L-1, R)
        if (t == 1) {
            int x;
            cin >> x;
            seg.range_apply(L, R, {ALL, 1ULL << (x - 1)});
        } else if (t == 2) {
            int x;
            cin >> x;
            seg.range_apply(L, R, {ALL ^ (1ULL << (x - 1)), 0});
        } else {
            Node res = seg.range_query(L, R);
            cout << res.mx << ' ' << res.cnt << '\n';
        }
    }
    return 0;
}

复杂度分析

• 时间复杂度：摊还 $O((N+Q)\log N + N\cdot\max x)$，其中 $\max x\le 60$
• 空间复杂度：$O(N)$