题目描述

在 Pigeland 有 $n$ 所大学，编号为 $1$ 到 $n$。每年，一些排名机构会发布这些大学的排名。今年共有 $k$ 份排名列表，每份列表都是 $1$ 到 $n$ 的一个排列，代表大学在该列表中的排名。对于每份排名，越靠近排列前面的大学排名越好。

:::align{center}

这是 2024 ICPC World Final 的真实故事。 :::

Supigar 是一名准备申请博士项目的大四学生，他有自己评判 $n$ 所大学综合水平的方法。他认为，如果满足下列条件之一，则大学 $x$ 被认为$\textit{优越于}$大学 $y$：

• $x$ 在至少一份排名中比 $y$ 排名更靠前，或者
• 存在某个 $z\ (z \neq x, z \neq y)$，使得 $x$ 在至少一份排名中比 $z$ 靠前，且 $z$ 优越于 $y$。

显然，在这种定义下，可能存在某些大学对 $(x, y)$ 关系满足 $x < y$ 时 $x$ 优越于 $y$，但同时 $y$ 也优越于 $x$。Supigar 将这类关系的大学对称为$\textit{模糊对}$。

Supigar 有 $q$ 个询问，第 $i$ 个询问由三个整数 $id_i$、$l_i$ 和 $r_i$ 表示（$l_i \le r_i$）。对于每个询问，他会关注第 $id_i$ 份排名列表中从第 $l_i$ 个位置到第 $r_i$ 个位置（两端都包含），对应的大学，并想知道在这些大学中，有多少对$(x, y)\,(x<y)$是模糊对。注意，模糊对的定义需综合考虑所有 $k$ 份排名列表的优越关系。

输入格式

有多组测试数据。输入的第一行为整数 $T$（$1 \leq T \leq 2 \times 10^5$），表示测试数据组数。对于每组测试数据：

第一行包含三个整数 $n$、$k$ 和 $q$（$1 \leq n, k, q \leq 2 \times 10^5$, $1 \leq n \times k \le 2 \times 10^5$），分别表示大学数、排名列表数和询问数。

接下来 $k$ 行，每行有 $n$ 个互不相同的整数 $a_{i,1}, a_{i,2}, \ldots, a_{i,n}$（$1 \le a_{i,j} \le n$），表示第 $i$ 份排名列表。

接下来 $q$ 行，每行有三个整数 $id_i'$、$l_i'$ 和 $r_i'$（$0 \le id_i' < k$, $0 \le l_i', r_i' < n$），表示经过编码的排名列表编号和询问区间。

• 真正的 $id_i$ 等于 $((id_i' + v_{i-1}) \bmod k) + 1$。
• 真正的 $l_i$ 等于 $((l_i' + v_{i-1}) \bmod n) + 1$。
• 真正的 $r_i$ 等于 $((r_i' + v_{i-1}) \bmod n) + 1$。

其中 $v_{i-1}$ 表示第 $(i-1)$ 个询问的答案。定义 $v_0 = 0$。由于采用了编码，你需要先计算出每次询问的答案才能处理下一个询问。保证 $1 \le id_i \le k$ 且 $1 \le l_i \le r_i \le n$。

还保证所有测试数据中 $n \times k$ 之和与 $q$ 之和都不超过 $2 \times 10^5$。

输出格式

对于每组测试数据，输出 $q$ 行。每行一个整数，表示第 $i$ 个询问的模糊对数量。

2
5 2 2
1 2 3 4 5
5 4 3 2 1
1 0 2
1 2 1
5 3 3
1 2 3 4 5
1 3 2 4 5
1 2 3 5 4
0 0 2
0 2 3
1 0 3

3
10
1
1
2

提示

对于第一个样例测试，经过解码后的两次询问分别为 $\texttt{2 1 3}$ 和 $\texttt{1 1 5}$。

对于第二个样例测试，经过解码后的三次询问分别为 $\texttt{1 1 3}$、$\texttt{2 4 5}$ 和 $\texttt{3 2 5}$。

由 ChatGPT 5 翻译