D1. 乌龟与 MEX 问题（简单版本） — 详细题解

---

一、问题重述

给定 $n$ 个序列，第 $i$ 个序列为 $a_{i,1}, a_{i,2}, \dots, a_{i,l_i}$。
初始有一个非负整数 $x = k$。每次操作可以选择一个序列 $i$，并将 $x$ 更新为：

$$x \leftarrow \operatorname{mex}(x, a_{i,1}, a_{i,2}, \dots, a_{i,l_i}) $$

其中 $\operatorname{mex}$ 定义为最小的未出现在集合中的非负整数。
操作可以进行任意多次（包括零次），同一个序列可以被重复选择。

定义 $f(k)$ 为从初始值 $k$ 出发，通过最优操作能达到的 最大 $x$ 值。

给定 $m$，需要计算：

$$\sum_{i=0}^{m} f(i) = f(0) + f(1) + \dots + f(m)$$

---

二、单个序列的性质

2.1 定义关键值

对于第 $i$ 个序列 $S_i = \{a_{i,1}, \dots, a_{i,l_i}\}$，定义两个重要值：

• 第一 MEX：$p_i = \operatorname{mex}(S_i)$，即 $S_i$ 中缺失的最小非负整数。
• 第二 MEX：$q_i = \operatorname{mex}(S_i \cup \{p_i\})$，即 $S_i$ 加上 $p_i$ 后缺失的最小非负整数。

注意：$q_i$ 也可以描述为 大于 $p_i$ 的第一个不在 $S_i$ 中的整数。

2.2 单次操作的效果

对序列 $i$ 执行一次操作，设当前值为 $x$：

情况 1：$x = p_i$

此时 $x$ 恰好是 $S_i$ 缺失的最小值。加上 $x$ 后，$p_i$ 被填补，因此新的 mex 变为下一个缺失值：

$$\operatorname{mex}(p_i, S_i) = q_i$$

情况 2：$x \neq p_i$

此时 $p_i$ 仍然不在 $S_i \cup \{x\}$ 中（因为 $x \neq p_i$），且所有小于 $p_i$ 的数都在 $S_i$ 中。因此最小缺失值仍是 $p_i$：

$$\operatorname{mex}(x, S_i) = p_i$$

总结（核心性质）：

$$\operatorname{mex}(x, S_i) = \begin{cases} q_i, & \text{if } x = p_i \\[4pt] p_i, & \text{if } x \neq p_i \end{cases} $$

---

三、可达值分析

3.1 从单个序列能到达的值

从任意 $x$ 出发，对序列 $i$ 重复操作：

• 若 $x \neq p_i$，一次操作后 $x$ 变为 $p_i$。
• 若 $x = p_i$，一次操作后 $x$ 变为 $q_i$。
• 若 $x = q_i$，由于 $q_i \neq p_i$，一次操作后 $x$ 变回 $p_i$。

因此，$p_i$ 和 $q_i$ 之间可以来回切换。从任意 $x$ 出发，最多两步就能到达 $q_i$（先到 $p_i$，再到 $q_i$）。

3.2 多个序列的协同

考虑所有 $n$ 个序列，设：

$$M = \max_{i=1}^{n} q_i$$

定理：从任意 $x \le M$ 出发，可以到达 $M$。

证明：

1. 取达到 $M$ 的那个序列 $j$，即 $q_j = M$。
2. 若当前 $x = p_j$，一步到 $M$。
3. 若当前 $x \neq p_j$，一步到 $p_j$，再一步到 $M$。
4. 若当前 $x$ 不是 $p_j$ 且无法直接到 $p_j$？实际上任何 $x$ 都可以通过合适的序列调整到 $p_j$ 吗？需要更细致的论证，但结论成立。

定理：从任意 $x > M$ 出发，无法到达大于 $x$ 的数。

证明：

• 任何操作的结果要么是某个 $p_i$（$\le M$），要么是某个 $q_i$（$\le M$）。
• 因此操作只会得到不超过 $M$ 的值。
• 由于 $x > M$，最优策略是 不进行任何操作，保留 $x$ 本身。

因此：

$$f(k) = \begin{cases} M, & \text{if } k \le M \\[4pt] k, & \text{if } k > M \end{cases} $$

其中 $M = \max\{q_1, q_2, \dots, q_n\}$。

---

四、求和公式

设 $M = \max_{i=1}^n q_i$。根据 $m$ 与 $M$ 的大小关系，分两种情况计算 $\displaystyle \sum_{k=0}^m f(k)$。

情况 1：$m \le M$

对所有 $k = 0, 1, \dots, m$，有 $f(k) = M$。
共有 $m+1$ 项，因此：

$$\sum_{k=0}^m f(k) = (m+1) \cdot M$$

情况 2：$m > M$

• 当 $k = 0, 1, \dots, M$ 时，$f(k) = M$，共 $M+1$ 项，贡献 $(M+1) \cdot M$。
• 当 $k = M+1, M+2, \dots, m$ 时，$f(k) = k$，这是一个等差数列：
  • 首项 $a_1 = M+1$
  • 末项 $a_n = m$
  • 项数 $n = m - M$

等差数列求和公式：

$$\sum_{k=M+1}^m k = \frac{(M+1 + m) \cdot (m - M)}{2} $$

总答案为：

$$\sum_{k=0}^m f(k) = (M+1) \cdot M + \frac{(M+1 + m)(m - M)}{2} $$

---

五、算法步骤

1. 对每个序列 $i$：
   • 将 $l_i$ 个元素存入集合（或排序后去重）。
   • 计算 $p_i$：从 $0$ 开始找第一个不在集合中的整数。
   • 计算 $q_i$：从 $p_i+1$ 开始找第一个不在集合中的整数。
2. 计算 $M = \max\{q_1, q_2, \dots, q_n\}$。
3. 根据 $m$ 与 $M$ 的关系，用上述公式计算答案。

时间复杂度：$O(\sum l_i \log l_i)$，满足 $2 \times 10^5$ 的限制。

---

六、代码实现（标程）

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

void solve() {
    int n;
    long long m;
    cin >> n >> m;
    
    int M = 0;  // 存储所有 q_i 的最大值
    
    for (int i = 0; i < n; i++) {
        int l;
        cin >> l;
        set<int> st;
        for (int j = 0; j < l; j++) {
            int x;
            cin >> x;
            st.insert(x);
        }
        
        // 计算 p_i（第一个缺失）
        int p = 0;
        while (st.count(p)) p++;
        
        // 计算 q_i（大于 p 的第一个缺失）
        int q = p + 1;
        while (st.count(q)) q++;
        
        M = max(M, q);
    }
    
    long long ans = 0;
    
    if (m <= M) {
        ans = (m + 1) * M;
    } else {
        ans = (long long)(M + 1) * M;               // 0..M 部分
        ans += (M + 1 + m) * (m - M) / 2;          // M+1..m 部分
    }
    
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

---

七、样例验证

样例 1

序列：

1. $\{0,2\}$：$p=1$，$q=3$
2. $\{2,3,3\}$：$p=0$，$q=1$
3. $\{7,0,1,5\}$：$p=2$，$q=3$

$M = \max(3, 1, 3) = 3$，$m = 4 > M$，情况 2：

$$\text{ans} = (3+1) \times 3 + \frac{(3+1+4)(4-3)}{2} = 4 \times 3 + \frac{8 \times 1}{2} = 12 + 4 = 16 $$

与样例输出一致 ✅

样例 2

序列：

1. $\{0,2,0,4,11\}$：去重后 $\{0,2,4,11\}$，$p=1$，$q=3$
2. $\{1,1\}$：$\{1\}$，$p=0$，$q=2$
3. $\{1,3,0,3,3\}$：$\{0,1,3\}$，$p=2$，$q=4$

$M = \max(3, 2, 4) = 4$，$m = 4 \le M$，情况 1：

$$\text{ans} = (4+1) \times 4 = 20$$

与样例输出一致 ✅

样例 4

序列：

1. $\{1,2\}$：$p=0$，$q=3$
2. $\{1,2\}$：$p=0$，$q=3$

$M = 3$，$m = 1 \le M$，情况 1：

$$\text{ans} = (1+1) \times 3 = 6$$

与样例输出一致 ✅

---

八、注意事项

1. 使用 long long 存储答案，因为 $m$ 可达 $10^9$，求和可能超过 $32$ 位整数范围。
2. $a_{i,j}$ 可能远大于 $n$，但寻找 $p_i$ 和 $q_i$ 时只需检查到 $l_i+2$ 即可，为简单起见直接用 set 存储所有值。
3. 输入数据量大，建议使用 ios::sync_with_stdio(false) 和 cin.tie(nullptr) 加速。