P14192 [ICPC 2024 Hangzhou R] Fuzzy Ranking

In Pigeland, there are $n$ universities, numbered from $1$ to $n$. Each year, several ranking organizations publish rankings of these universities. This year, there are $k$ ranking lists, where each list is a permutation of integers from $1$ to $n$, representing the universities. In each ranking, the closer a university is to the beginning of the permutation, the better its ranking is in this list. :::align{center}  A true story in the 2024 ICPC World Final. ::: Supigar, a year-4 student who wants to apply for PhD programs in Pigeland, has his own method to evaluate the $n$ universities comprehensively. He considers that university $x$ is $\textit{superior}$ to another university $y$ if and only if: - $x$ is ranked better than $y$ in at least one list, or - $x$ is ranked better than $z\ (z \neq x, z \neq y)$ in at least one list, and $z$ is superior to $y$. Clearly, under this definition, there might exist some pairs of universities $x$ and $y$ ($x < y$) such that $x$ is superior to $y$ while $y$ is also superior to $x$. Supigar calls such pairs $\textit{fuzzy}$. Supigar has $q$ queries, where the $i$-th query can be represented by three integers $id_i$, $l_i$ and $r_i$ ($l_i \le r_i$). For each query, he will consider the $id_i$-th rank list and all the universities between the $l_i$-th position and the $r_i$-th position (both inclusive) in that list. He wants to know, among these universities, how many pairs of them are fuzzy. Note that the definition of fuzzy pairs requires considering the superior relationships among all $k$ rank lists.

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \leq T \leq 2 \times 10^5$) indicating the number of test cases. For each test case: The first line contains three integers $n$, $k$, and $q$ ($1 \le n, k, q \leq 2 \times 10^5$, $1 \leq n \times k \le 2 \times 10^5$) indicating the number of universities, rank lists, and queries, respectively. For the following $k$ lines, the $i$-th line contains $n$ distinct integers $a_{i,1}, a_{i,2}, \ldots, a_{i,n}$ ($1 \le a_{i,j} \le n$) indicating the $i$-th rank list. For the following $q$ lines, the $i$-th line contains three integers $id_i'$, $l_i'$, and $r_i'$ ($0 \le id_i' < k$, $0 \le l_i', r_i' < n$) indicating the $\textbf{encoded}$ index of the rank list and the query range for the $i$-th query. - The real value of $id_i$ is equal to $((id_i' + v_{i - 1}) \bmod k) + 1$. - The real value of $l_i$ is equal to $((l_i' + v_{i - 1}) \bmod n) + 1$. - The real value of $r_i$ is equal to $((r_i' + v_{i - 1}) \bmod n) + 1$. Where $v_{i - 1}$ is the answer for the $(i - 1)$-th query. Specifically, we define $v_0 = 0$. With the encoded queries, you're forced to calculate the answer to each query before processing the next one. It's guaranteed that $1 \le id_i \le k$ and $1 \le l_i \le r_i \le n$ after decoding. It is also guaranteed that neither the sum of $n \times k$ nor the sum of $q$ of all test cases will exceed $2 \times 10^5$.

For each test case output $q$ lines. Each line contains a single integer representing the number of fuzzy pairs as the answer to the $i$-th query.

For the first sample test case, the two decoded queries are $\texttt{2 1 3}$ and $\texttt{1 1 5}$. For the second sample test case, the three decoded queries are $\texttt{1 1 3}$, $\texttt{2 4 5}$, and $\texttt{3 2 5}$.