← 返回题目列表

Codeforces · 2003/D2

D2. 海龟和 MEX 问题(困难版)

中文机器翻译题面 查看原题

两个版本是不同的问题。在此版本的问题中,您不能两次或多次选择相同的整数。只有两个版本都解决了,你才能进行黑客攻击。

有一天,Turtle 正在玩 $$$n$$$ 序列。令第 $$$i$$$ 个序列的长度为 $$$l_i$$$。那么第 $$$i$$$ 个序列是 $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, l_i}$$$。

当乌龟玩耍时,小猪给了乌龟一个需要解决的问题。问题的表述是:

- 首先有一个非负整数$$$x$$$。 Turtle 将对整数执行任意数量(可能为零)的运算。
- 在每个操作中,Turtle 可以选择一个整数 $$$i$$$,使得 $$$1 \le i \le n$$$ 和 $$$i$$$ 之前没有被选择,并将 $$$x$$$ 设置为 $$$\text{mex}^{\dagger}(x, a_{i, 1}, a_{i, 2}, \ldots, a_{i, l_i})$$$。
- Turtle 被要求找到答案,即执行任意次数的操作后 $$$x$$$ 的最大值。

Turtle毫不费力地解决了上述问题。当$$$x$$$的初始值为$$$k$$$时,他将$$$f(k)$$$定义为上述问题的答案。

然后 Piggy 给 Turtle 一个非负整数 $$$m$$$ 并要求 Turtle 求 $$$\sum\limits_{i = 0}^m f(i)$$$ 的值(即 $$$f(0) + f(1) + \ldots + f(m)$$$ 的值)。不幸的是,他无法解决这个问题。请帮助他!

$$$^{\dagger}\text{mex}(c_1, c_2, \ldots, c_k)$$$ 被定义为序列 $$$c$$$ 中不出现的最小非负整数 $$$x$$$。例如,$$$\text{mex}(2, 2, 0, 3)$$$ 为 $$$1$$$,$$$\text{mex}(1, 2)$$$ 为 $$$0$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n, m$$$ ($$$1 \le n \le 2 \cdot 10^5, 0 \le m \le 10^9$$$)。

以下 $$$n$$$ 行中的每一行都包含几个整数。第一个整数 $$$l_i$$$ ($$$1 \le l_i \le 2 \cdot 10^5$$$) 表示第 $$$i$$$ 个序列的长度,后面的 $$$l_i$$$ 整数 $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, l_i}$$$ ($$$0 \le a_{i, j} \le 10^9$$$) 表示第 $$$i$$$ 序列的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$,所有测试用例的 $$$\sum l_i$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - $$$\sum\limits_{i = 0}^m f(i)$$$ 的值。

示例

输入 #1

6
3 4
2 0 2
3 2 3 3
4 7 0 1 5
3 4
5 0 2 0 4 11
1 1
5 1 3 0 3 3
2 50
2 1 2
2 1 2
1 1
7 1 2 4 1 4 9 5
4 114514
2 2 2
5 7 3 6 0 3
3 0 1 1
5 0 9 2 1 5
5 1919810
1 2
2 324003 0
3 1416324 2 1460728
4 1312631 2 0 1415195
5 1223554 192248 2 1492515 725556

输出 #1

16
18
1281
4
6556785365
1842836177961

注意

在第一个测试用例中,当 $$$x$$$ 最初为 $$$2$$$ 时,Turtle 可以选择 $$$i = 3$$$ 并将 $$$x$$$ 设置为 $$$\text{mex}(x, a_{3, 1}, a_{3, 2}, a_{3, 3}, a_{3, 4}) = \text{mex}(2, 7, 0, 1, 5) = 3$$$。可以证明Turtle无法让$$$x$$$的值大于$$$3$$$,所以$$$f(2) = 3$$$。

可以看出,$$$f(0) = 3$$$、$$$f(1) = 3$$$、$$$f(2) = 3$$$、$$$f(3) = 3$$$ 和 $$$f(4) = 4$$$。所以 $$$f(0) + f(1) + f(2) + f(3) + f(4) = 3 + 3 + 3 + 3 + 4 = 16$$$。

在第二个测试用例中,当 $$$x$$$ 最初为 $$$1$$$ 时,Turtle 可以选择 $$$i = 1$$$ 并将 $$$x$$$ 设置为 $$$\text{mex}(x, a_{1, 1}, a_{1, 2}, a_{1, 3}, a_{1, 4}, a_{1, 5}) = \text{mex}(1, 0, 2, 0, 4, 11) = 3$$$。可以证明Turtle无法让$$$x$$$的值大于$$$3$$$,所以$$$f(1) = 3$$$。

可以看出,$$$f(0) = 4$$$、$$$f(1) = 3$$$、$$$f(2) = 4$$$、$$$f(3) = 3$$$ 和 $$$f(4) = 4$$$。所以 $$$f(0) + f(1) + f(2) + f(3) + f(4) = 4 + 3 + 4 + 3 + 4 = 18$$$。

在第四个测试用例中,可以看出 $$$f(0) = 3$$$ 和 $$$f(1) = 1$$$。所以 $$$f(0) + f(1) = 3 + 1 = 4$$$。