NOI '22 P1 - Major

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.5s
Memory limit: 1G

Problem type

In this problem, the mode of a sequence is the number that appears strictly more than half the times in the sequence. Please refer to this definition in the problem.

Initially, n positive integer sequences of different lengths are given, numbered from 1 to n, and the sequences can be empty. These n sequences are considered to exist, and the sequences corresponding to other numbers are considered to be non-existent.

There are q operations, and operations are of the following types:

  • 1\ x\ y: Insert the number y at the end of sequence x. It is guaranteed that sequence x exists and 1 \le x, y \le n + q.
  • 2\ x: Delete the number at the end of sequence x. It is guaranteed that sequence x exists, is not empty, and 1 \le x \le n + q.
  • 3\ m\ x_1\ x_2\ ...\ x_m: Concatenate sequences x_1, x_2, \ldots, x_m to get a new sequence and return its mode. Return -1 if the mode does not exist. The data guarantees that for any 1 \le i \le m the sequence numbered x_i still exists, 1 \le x_i \le n + q, and the concatenated sequence is non-empty. There is no guarantee that x_i are distinct. The concatenation done here won't affect future operations.
  • 4\ x_1\ x_2\ x_3: Create a new sequence numbered x_3, which is the concatenation of sequence x_1 and sequence x_2. Then, delete the sequences numbered x_1 and x_2. After this operation, sequence x_3 is considered to exist, and the sequences x_1 and x_2 are considered to be non-existent and will not be used again in subsequent operations. It is guaranteed that 1 \le x_1, x_2, x_3 \le n + q, x_1 \ne x_1, the sequences x_1 and x_2 existed before the operation, and no operation used the sequence numbered x_3 before the operation.

Input Specification

The first line of input contains two positive integers n and q, which represent the number of initial sequences and the number of operations, respectively. It is guaranteed that n, q \le 5 \times 10^5.

In the next n lines, the i-th line represents the sequence numbered i. The first non-negative integer l_i of each line represents the length of the i-th sequence, followed by l_i non-negative integers a_{i,j} representing the elements of the sequence in order. Let C_l = \Sigma l_i represent the sum of the input sequence lengths, then it is guaranteed that C_l \le 5 \times 10^5 and a_{i,j} \le n + q.

Each of the next q lines represent an operation in the format described above, consisting of several integers. Let C_m = \Sigma m represent the sum of all sequences that need to be concatenated in operation 3, then it is guaranteed that C_m \leq 5 \times 10^{5}.

Output Specification

For each type 3 query, output an integer on a new line, the answer to the query.

Samples

Sample inputs and outputs can be found here.

Sample Input 1

2 8
3 1 1 2
3 3 3 3
3 1 1
3 1 2
4 2 1 3
3 1 3
2 3
3 1 3
1 3 1
3 1 3

Sample Output 1

1
3
-1
3
-1

Explanation for Sample 1

The first query queries the mode of sequence 1. Since the sequence contains two 1s, more than half the length of the sequence, the mode is 1. The second query queries the mode of sequence 2. Since the sequence contains only 3s, the mode is 3. The third query asks for the mode of sequence 3. At this time, sequence 3 is (1, 1, 2, 3, 3, 3), and there is no number occuring more than 3 times, so the output is -1.

Sample Input 2

4 9
1 1
1 2
1 3
1 4
3 4 1 2 3 4
1 1 2
3 2 1 2
2 3
3 3 1 2 3
1 4 4
1 4 4
1 4 4
3 4 1 2 3 4

Sample Output 2

-1
2
2
4

Explanation of Sample 2

The first query asks for the mode obtained after concatenating sequences 1, 2, 3, 4. The result of concatenation is (1, 2, 3, 4), and there is no number with more than two occurrences, so the output is -1. The fourth query is the mode of the sequence obtained after concatenating sequences 1, 2, 3, 4. The result of the concatenation is (1, 2, 2, 4, 4, 4, 4), which has a mode of 4.

Sample 3

See major3.in and major3.ans in the attachment package. This example satisfies the constraints of test cases 1∼3.

Sample 4

See major4.in and major4.ans in the attachment package. This example satisfies the constraints of test cases 11∼12.

Constraints

For all test data, it is guaranteed that 1 \le n, q, C_m, C_l \le 5 \times 10^{5}.

Test Case n, q, C_m, C_l \le Additional Constraints
1~3 300 Property C
4~7 4000 Property C
8 10^5 Property A, B
9 Property A
10 Property B
11, 12 Property C
13 None
14 5 \times 10^5 Property A, B, C
15 Property A
16 Property B
17, 18 Property C
19, 20 None

Special properties:

  • Property A: n = 1, no operations of type 4.
  • Property B: At any time, the sequences contain only 1s and 2s.
  • Property C: No operations of type 2.

Comments

There are no comments at the moment.