P16657 [GKS 2018 #G] Combining Classes

Supervin is teaching $N$ classes, which are numbered from $1$ to $N$. After giving his most recent exam, he noticed that in each of his classes, the test scores of his students form a sequence of consecutive integers. Therefore, Supervin can summarize the scores for the i-th class as two integers $L_i$ and $R_i$. This means that the i-th class has $R_i - L_i + 1$ students, and for each $x$ ($L_i \le x \le R_i$), there is exactly one student with score $x$. Supervin would like to combine the scores from the students from all of his classes and sort the scores in non-increasing order. He has $Q$ questions (numbered from $1$ to $Q$) about this list; for the i-th question, he wants to know what the $K_i$-th highest score is. (If $K_i$ is greater than the number of students, then the answer for the i-th question is $0$.) Can you help Supervin answer all of his questions? Since there may be many answers, instead of outputting all of them, output proof that you have answered them: the sum of $(S_i \times i)$ for all $1 \le i \le Q$, where $S_i$ is the answer to the i-th question.

The first line of the input gives the number of test cases, T. T test cases follow. Each test case contains four lines. The first line contains two integers N and Q as described above. The next three lines each contain six integers in the following format, respectively: - $X_1$ $X_2$ $A_1$ $B_1$ $C_1$ $M_1$ - $Y_1$ $Y_2$ $A_2$ $B_2$ $C_2$ $M_2$ - $Z_1$ $Z_2$ $A_3$ $B_3$ $C_3$ $M_3$ These values are used to generate $L_i$, $R_i$, and $K_i$ as follows: We define: - $X_i = (A_1 \times X_{i - 1} + B_1 \times X_{i - 2} + C_1)$ modulo $M_1$, for i = 3 to N. - $Y_i = (A_2 \times Y_{i - 1} + B_2 \times Y_{i - 2} + C_2)$ modulo $M_2$, for i = 3 to N. - $Z_i = (A_3 \times Z_{i - 1} + B_3 \times Z_{i - 2} + C_3)$ modulo $M_3$, for i = 3 to Q. We also define: - $L_i = \min(X_i, Y_i) + 1$, for i = 1 to N. - $R_i = \max(X_i, Y_i) + 1$, for i = 1 to N. - $K_i = Z_i + 1$, for i = 1 to Q.

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the sum of $(S_i \times i)$ for all $1 \le i \le Q$, where $S_i$ is the answer to the i-th question.

In Sample Case #1, the generated arrays X, Y, Z are: - $X = [3, 1, 3, 0, 8]$. - $Y = [2, 7, 7, 2, 6]$. - $Z = [4]$. Therefore, - $L = [3, 2, 4, 1, 7]$. - $R = [4, 8, 8, 3, 9]$. - $K = [5]$. The students' scores for each of the classes are $[3, 4]$, $[2, 3, 4, 5, 6, 7, 8]$, $[4, 5, 6, 7, 8]$, $[1, 2, 3]$, and $[7, 8, 9]$. This means that the students' scores for all classes combined are $[3, 4, 2, 3, 4, 5, 6, 7, 8, 4, 5, 6, 7, 8, 1, 2, 3, 7, 8, 9]$. If we sort them in non-increasing order, they are $[9, 8, 8, 8, 7, 7, 7, 6, 6, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 1]$. Therefore, the student with the 5th highest score has score 7. Thus, $S = [7]$ and the answer is $7 \times 1 = 7$. ### Limits $1 \le T \le 100$. $1 \le N \le 4 \times 10^5$. $0 \le A_i < M_i$, for all i. $0 \le B_i < M_i$, for all i. $0 \le C_i < M_i$, for all i. $0 \le X_1 < M_1$. $0 \le X_2 < M_1$. $0 \le Y_1 < M_2$. $0 \le Y_2 < M_2$. $0 \le Z_1 < M_3$. $0 \le Z_2 < M_3$. $1 \le M_i \le 10^9$, for all i. **Small dataset (Test set 1 - Visible)** $Q = 1$. **Large dataset (Test set 2 - Hidden)** $1 \le Q \le 10^5$.