【Codeforces】CF 2003 D2

Turtle and a MEX Problem (Hard Version)

#图论 #贪心 #数学

题目描述

The two versions are different problems. In this version of the problem, you can’t choose the same integer twice or more. You can make hacks only if both versions are solved. One day, Turtle was playing with n n n sequences. Let the length of the i i i-th sequence be l i l_i li. Then the i i i-th sequence was a i , 1 , a i , 2 , … , a i , l i a_{i, 1}, a_{i, 2}, \ldots, a_{i, l_i} ai,1,ai,2,,ai,li. Piggy gave Turtle a problem to solve when Turtle was playing. The statement of the problem was: - There was a non-negative integer x x x at first. Turtle would perform an arbitrary number (possibly zero) of operations on the integer. - In each operation, Turtle could choose an integer i i i such that 1 ≤ i ≤ n 1 \le i \le n 1in and i i i wasn’t chosen before, and set x x x to mex † ( x , a i , 1 , a i , 2 , … , a i , l i ) \text{mex}^{\dagger}(x, a_{i, 1}, a_{i, 2}, \ldots, a_{i, l_i}) mex(x,ai,1,ai,2,,ai,li). - Turtle was asked to find the answer, which was the maximum value of x x x after performing an arbitrary number of operations. Turtle solved the above problem without difficulty. He defined f ( k ) f(k) f(k) as the answer to the above problem when the initial value of x x x was k k k. Then Piggy gave Turtle a non-negative integer m m m and asked Turtle to find the value of ∑ i = 0 m f ( i ) \sum\limits_{i = 0}^m f(i) i=0mf(i) (i.e., the value of f ( 0 ) + f ( 1 ) + … + f ( m ) f(0) + f(1) + \ldots + f(m) f(0)+f(1)++f(m)). Unfortunately, he couldn’t solve this problem. Please help him! † mex ( c 1 , c 2 , … , c k ) ^{\dagger}\text{mex}(c_1, c_2, \ldots, c_k) mex(c1,c2,,ck) is defined as the smallest non-negative integer x x x which does not occur in the sequence c c c. For example, mex ( 2 , 2 , 0 , 3 ) \text{mex}(2, 2, 0, 3) mex(2,2,0,3) is 1 1 1, mex ( 1 , 2 ) \text{mex}(1, 2) mex(1,2) is 0 0 0.

输入格式

Each test contains multiple test cases. The first line contains the number of test cases t t t ( 1 ≤ t ≤ 1 0 4 1 \le t \le 10^4 1t104). The description of the test cases follows.

The first line of each test case contains two integers n , m n, m n,m ( 1 ≤ n ≤ 2 ⋅ 1 0 5 , 0 ≤ m ≤ 1 0 9 1 \le n \le 2 \cdot 10^5, 0 \le m \le 10^9 1n2105,0m109).

Each of the following n n n lines contains several integers. The first integer l i l_i li ( 1 ≤ l i ≤ 2 ⋅ 1 0 5 1 \le l_i \le 2 \cdot 10^5 1li2105) represents the length of the i i i-th sequence, and the following l i l_i li integers a i , 1 , a i , 2 , … , a i , l i a_{i, 1}, a_{i, 2}, \ldots, a_{i, l_i} ai,1,ai,2,,ai,li ( 0 ≤ a i , j ≤ 1 0 9 0 \le a_{i, j} \le 10^9 0ai,j109) represent the elements of the i i i-th sequence.

It is guaranteed that the sum of n n n over all test cases does not exceed 2 ⋅ 1 0 5 2 \cdot 10^5 2105 and the sum of ∑ l i \sum l_i li over all test cases does not exceed 2 ⋅ 1 0 5 2 \cdot 10^5 2105.

输出格式

For each test case, output a single integer — the value of ∑ i = 0 m f ( i ) \sum\limits_{i = 0}^m f(i) i=0mf(i).

样例 #1

样例输入 #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

解法

解题思路

首先,我们定义一个数列的 m e x mex mex m e x 1 mex1 mex1,填充上这个 m e x mex mex出现的新的 m e x mex mex称为 m e x 2 mex2 mex2,那么,对于比所有数列中最大的 m e x 2 mex2 mex2还要大的数,一定无法变成另外一个数,因此,对于这一部分,我们直接通过等差数列来求和即可。

而对于小于这一部分的数呢,就 3 3 3种情况:

1. 1. 1.这个数不等于这个数列的 m e x 1 mex1 mex1,因此这个数可以变成 m e x 1 mex1 mex1

2. 2. 2.这个数是一个数列的 m e x 1 mex1 mex1,因此这个数可以成为这个数列的 m e x 2 mex2 mex2

3. 3. 3.这个数是一个数列的 m e x 1 mex1 mex1 m e x 2 mex2 mex2,并且这个 m e x 1 / m e x 2 mex1/mex2 mex1/mex2可以成为另一个数列的 m e x 1 mex1 mex1,因此它也可以成为另一个数列的 m e x 2 mex2 mex2

综上,我们可以预处理出所有数列的 m e x 1 mex1 mex1 m e x 2 mex2 mex2,然后让 m e x 1 mex1 mex1 m e x 2 mex2 mex2连边。

由于题目中保证 ∑ l i \sum l_i li 不超过

上一篇:MySQL常用SQL语句(持续更新中)-数据库相关


下一篇:案例-表白墙简单实现