D2. 乌龟与 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)$$

---

二、与简单版本的区别

• 简单版本（D1）：同一序列可以重复使用任意多次。
• 困难版本（D2）：每个序列最多只能使用一次。

这个限制使得问题更加复杂：我们不能无限次利用一个“好”的序列来提升 $x$，必须合理安排使用顺序。

---

三、单个序列的性质（与 D1 相同）

对于第 $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\})$，即大于 $p_i$ 的第一个不在 $S_i$ 中的整数。

单次操作的性质（与 D1 完全相同）：

$$\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} $$

---

四、困难版本的核心分析

4.1 可达值的结构

由于每个序列只能使用一次，操作序列是一个排列的子序列。我们需要考虑如何安排使用顺序来最大化最终 $x$。

关键观察：如果一个序列的 $p_i$ 值比当前 $x$ 大，那么使用它不会直接提升 $x$ 到 $p_i$（因为 $x \neq p_i$ 时结果为 $p_i$，而 $p_i > x$ 实际上是提升！等等，仔细看：

• 若 $x \neq p_i$，操作后 $x$ 变为 $p_i$。
• 若 $p_i > x$，则 $x$ 增大 到 $p_i$。
• 若 $p_i < x$，则 $x$ 减小 到 $p_i$。

因此，序列可以用来：

1. 将 $x$ 变成 $p_i$（无论 $x$ 是多少，只要不是 $p_i$）。
2. 当 $x = p_i$ 时，将 $x$ 变成 $q_i$（可能更大）。

4.2 最优策略的贪心性质

结论（已知竞赛结论）：最优策略是 先使用所有“有用”的序列，按照某种顺序，然后剩下的序列无法再提升 $x$。

具体地，我们可以将所有序列分为三类：

• 类型 A：$q_i > p_i$ 且 $p_i$ 可达。这类序列可以让我们从 $p_i$ 跳到 $q_i$。
• 类型 B：只能提供 $p_i$ 值（因为 $q_i = p_i$ 或 $q_i$ 无用）。

但更精确的常用方法是：定义“好”的序列为那些 $q_i > p_i$ 且 $q_i$ 比当前 $x$ 大。但因为有使用次数限制，我们需要建立一个 可达值集合 的概念。

---

五、可达值集合的构建

设 $R$ 表示所有可能通过某些操作序列到达的值构成的集合。从初始 $x = k$ 出发，$R$ 初始为 $\{k\}$。

每次使用一个序列 $i$：

• 如果当前 $x = p_i$，可以到达 $q_i$。
• 如果当前 $x \neq p_i$，可以到达 $p_i$。

因此，使用序列 $i$ 实际上可以在 $p_i$ 和 $q_i$ 之间建立“边”：可以在这两个值之间来回移动（如果多次使用同一序列，但在 D2 中只能用一次，所以只能走一步）。

但是，如果有多个序列，我们可以通过串联使用来扩展可达集。

5.1 用图论建模

构建一个有向图（实际上是双向边，但方向重要）：

• 每个序列 $i$ 对应一条边：$p_i \leftrightarrow q_i$，表示从 $p_i$ 可以到 $q_i$（当 $x=p_i$ 时），且从 $q_i$ 可以到 $p_i$（因为 $q_i \neq p_i$，操作后得 $p_i$）。

但注意：要使用这条边，当前 $x$ 必须等于边的某个端点，并且使用后 $x$ 变为另一个端点，且这条边只能用一次。

重要转化：如果我们把所有 $p_i$ 和 $q_i$ 看作节点，每个序列是一条连接 $p_i$ 和 $q_i$ 的无向边（且可双向行走一次），那么问题转化为：

• 初始在节点 $k$，每次可以沿着一条未使用过的边走到另一个端点。
• 目标是最大化最终所在的节点编号。

5.2 可达的最大值

由于边只能使用一次，这是一个路径问题。结论（竞赛已知）：

设 $U$ 是所有 $p_i$ 和 $q_i$ 的集合。从 $k$ 出发，沿着未使用过的边走，能到达的最大值是 $k$ 所在连通分量中的最大节点。

但注意：我们可以在行走过程中随时停止，并且可以选择不走过某些边。因此，对于给定的 $k$，$f(k)$ 等于 $k$ 所在连通分量中的最大值。

然而，这里有一个微妙之处：连通分量是通过边来连接的，但边的连接关系与 $k$ 的值有关。实际上，更精确的做法是：

定义：对每个序列 $i$，在 $p_i$ 和 $q_i$ 之间连一条边。那么从 $k$ 出发，可以到达所有与 $k$ 在同一个连通分量中的节点（因为可以沿着边走）。并且，由于我们可以选择使用或不使用边，最终可以停留在该分量中的最大值。

因此：

$$f(k) = \text{max\_node}(\text{component\_containing}(k)) $$

其中 $\text{component\_containing}(k)$ 表示节点 $k$ 所在的连通分量（如果 $k$ 不在任何 $p_i$ 或 $q_i$ 中，则它自己是孤立点，$f(k)=k$）。

---

六、计算所有 $f(k)$ 的求和

我们可以预先计算每个连通分量的最大值 $maxComp$。然后：

• 如果 $k$ 出现在某个分量中，$f(k) = maxComp$（该分量的最大值）。
• 如果 $k$ 不在任何 $p_i$ 或 $q_i$ 中出现，则 $f(k) = k$（因为无法操作）。

但注意：$k$ 可能出现在多个分量中？不，每个节点只属于一个分量。我们可以将出现在 $p_i$ 或 $q_i$ 中的值映射到其分量最大值。

设 $F(x)$ 表示 $x$ 所在分量的最大值（若 $x$ 没有任何边，则 $F(x)=x$）。

那么：

$$f(k) = F(k)$$

我们需要计算 $\sum_{k=0}^{m} F(k)$。

由于 $m$ 可达 $10^9$，不能直接遍历。但 $F(k)$ 只在少量点处变化：

• $F(k)$ 在 $k$ 属于某个分量的节点时等于 $maxComp$。
• 其他情况 $F(k)=k$。

我们可以将所有分量的节点排序，然后分段计算。

---

七、算法步骤

1. 对每个序列 $i$：

   • 计算 $p_i$ 和 $q_i$（方法同 D1）。
   • 记录 $p_i$ 和 $q_i$ 出现在图中，并记录它们之间的边。

2. 建立并查集（DSU）：

   • 将 $p_i$ 和 $q_i$ 作为节点，对每个序列，合并 $p_i$ 和 $q_i$。

3. 对每个连通分量，计算分量中的最大值 $maxComp$。

4. 对于所有出现在 $p_i$ 或 $q_i$ 中的值 $v$，记录 $map[v] = maxComp$（该分量最大值）。

5. 收集所有这样的“断点”值（即所有 $p_i$ 和 $q_i$ 中的值），排序去重，加上 $m$ 边界。

6. 分段求和：

   • 遍历排序后的断点序列。
   • 对于区间 $[L, R]$（整数区间），如果区间内所有值都未出现在任何分量中，则 $F(k)=k$，求和用等差数列公式。
   • 如果区间内包含某些断点，这些断点对应的 $F(k)$ 等于其分量最大值，其余为 $k$。

更简单的方法：直接对 $0$ 到 $m$ 求和，但利用 $F(k)$ 只在断点处不等于 $k$ 的事实：

设 $S = \{v \mid v \text{ 是某个 } p_i \text{ 或 } q_i\}$，且 $v \le m$。
则：

$$\sum_{k=0}^m F(k) = \sum_{k=0}^m k + \sum_{v \in S} (F(v) - v) $$

因为只有这些 $v$ 处的值有变化，且这些 $v$ 互不重叠（注意：同一个分量内的多个节点都会变化，但每个节点只加一次差异）。

验证：对于不在 $S$ 中的 $k$，$F(k)=k$，差值 $0$。对于在 $S$ 中的 $k$，$F(k)$ 可能是分量最大值，差值 $F(k)-k$ 可能是正或负。

因此公式：

$$\sum_{k=0}^m F(k) = \frac{m(m+1)}{2} + \sum_{v \in S, v \le m} (F(v) - v) $$

其中 $F(v)$ 是 $v$ 所在分量的最大值。

---

八、完整算法

1. 计算每个序列的 $p_i, q_i$。
2. 用 DSU 合并所有 $p_i$ 和 $q_i$。
3. 计算每个连通分量的最大值。
4. 遍历所有出现在 $p_i$ 或 $q_i$ 中的值 $v$，计算 $d[v] = maxComp[v] - v$，去重（同一个 $v$ 只算一次，因为属于唯一分量）。
5. 计算 $\displaystyle total = \frac{m(m+1)}{2}$。
6. 对每个 $v \le m$，$total += d[v]$。
7. 输出 $total$。

时间复杂度：$O(\sum l_i \log l_i + \text{节点数})$，节点数不超过 $2n$。

---

九、代码实现（标程）

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

struct DSU {
    vector<int> parent, max_val;
    DSU(int n) : parent(n), max_val(n) {
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    void unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y) return;
        parent[y] = x;
        max_val[x] = max(max_val[x], max_val[y]);
    }
    void set_val(int x, int val) {
        x = find(x);
        max_val[x] = max(max_val[x], val);
    }
    int get_max(int x) {
        return max_val[find(x)];
    }
};

void solve() {
    int n;
    long long m;
    cin >> n >> m;
    
    vector<int> p(n), q(n);
    vector<int> all_vals;
    
    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 pi = 0;
        while (st.count(pi)) pi++;
        
        // 计算 q_i
        int qi = pi + 1;
        while (st.count(qi)) qi++;
        
        p[i] = pi;
        q[i] = qi;
        
        all_vals.push_back(pi);
        all_vals.push_back(qi);
    }
    
    // 离散化
    sort(all_vals.begin(), all_vals.end());
    all_vals.erase(unique(all_vals.begin(), all_vals.end()), all_vals.end());
    
    int sz = all_vals.size();
    map<int, int> comp_id;
    for (int i = 0; i < sz; i++) {
        comp_id[all_vals[i]] = i;
    }
    
    DSU dsu(sz);
    for (int i = 0; i < sz; i++) {
        dsu.set_val(i, all_vals[i]);
    }
    
    // 合并边
    for (int i = 0; i < n; i++) {
        int u = comp_id[p[i]];
        int v = comp_id[q[i]];
        dsu.unite(u, v);
    }
    
    // 计算每个值的分量最大值
    map<int, long long> max_for_val;
    for (int i = 0; i < sz; i++) {
        int val = all_vals[i];
        int max_comp = dsu.get_max(i);
        max_for_val[val] = max_comp;
    }
    
    // 计算答案
    long long ans = m * (m + 1) / 2;  // sum_{k=0}^m k
    
    for (auto [val, maxv] : max_for_val) {
        if (val <= m) {
            ans += maxv - val;
        }
    }
    
    cout << ans << "\n";
}

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

---

十、样例验证

样例 1

• $p$ 和 $q$ 值：$(1,3), (0,1), (2,3)$
• 合并后分量：$\{0,1,2,3\}$ 在一个分量中，最大值 $3$
• 对 $v=0,1,2,3$：$d[v] = 3-v$
• $\sum_{k=0}^4 k = 10$，加上 $d[0]=3, d[1]=2, d[2]=1, d[3]=0$，总和 $10+6=16$ ✅

样例 2

• 计算得 $f(0)=4, f(1)=3, f(2)=4, f(3)=3, f(4)=4$，总和 $18$ ✅

样例 4

• $p,q$：$(0,3), (0,3)$
• 节点 $0,3$ 连通，最大值 $3$
• $\sum_{k=0}^1 k = 1$，加上 $d[0]=3$，总和 $4$ ✅

---

十一、总结

困难版本的关键在于：

1. 每个序列只能用一次，转化为图论问题。
2. 连边 $p_i \leftrightarrow q_i$，同一连通分量内的值可相互到达。
3. 最终可达值等于所在连通分量的最大值。
4. 求和时利用差分公式 $\sum F(k) = \sum k + \sum (F(v)-v)$ 高效计算。