CF1917D.Yet Another Inversions Problem

You are given a permutation $p_0, p_1, \ldots, p_{n-1}$ of odd integers from $1$ to $2n-1$ and a permutation $q_0, q_1, \ldots, q_{k-1}$ of integers from $0$ to $k-1$.

An array $a_0, a_1, \ldots, a_{nk-1}$ of length $nk$ is defined as follows:

$a_{i \cdot k+j}=p_i \cdot 2^{q_j}$ for all $0 \le i \lt n$ and all $0 \le j \lt k$

For example, if $p = [3, 5, 1]$ and $q = [0, 1]$, then $a = [3, 6, 5, 10, 1, 2]$.

Note that all arrays in the statement are zero-indexed. Note that each element of the array $a$ is uniquely determined.

Find the number of inversions in the array $a$. Since this number can be very large, you should find only its remainder modulo $998\,244\,353$.

An inversion in array $a$ is a pair $(i, j)$ ($0 \le i \lt j \lt nk$) such that $a_i \gt a_j$.

给你一个由 $1$ 到 $2n-1$ 的奇数组成的排列 $p_0, p_1, \ldots, p_{n-1}$，以及一个由 $0$ 到 $k-1$ 的整数组成的排列 $q_0, q_1, \ldots, q_{k-1}$。

定义一个长度为 $nk$ 的数组 $a_0, a_1, \ldots, a_{nk-1}$ 如下：

对所有满足 $0 \le i \lt n$ 和 $0 \le j \lt k$ 的 $i, j$，有

$$a_{i \cdot k+j}=p_i \cdot 2^{q_j}$$

例如，若 $p = [3, 5, 1]$ 且 $q = [0, 1]$，则 $a = [3, 6, 5, 10, 1, 2]$。

注意：题目中所有数组均采用零起点索引（zero-indexed）。注意：数组 $a$ 的每个元素均由上述规则唯一确定。

请计算数组 $a$ 中逆序对（inversion）的个数。由于该数目可能非常大，你只需输出其对 $998\,244\,353$ 取模的结果。

数组 $a$ 中的一个逆序对是指一对下标 $(i, j)$（满足 $0 \le i \lt j \lt nk$），使得 $a_i \gt a_j$。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $k$ ($1 \le n, k \le 2 \cdot 10^5$) — the lengths of arrays $p$ and $q$.

The second line of each test case contains $n$ distinct integers $p_0, p_1, \ldots, p_{n-1}$ ($1 \le p_i \le 2n-1$, $p_i$ is odd) — the array $p$.

The third line of each test case contains $k$ distinct integers $q_0, q_1, \ldots, q_{k-1}$ ($0 \le q_i \lt k$) — the array $q$.

It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$ and the sum of $k$ over all test cases doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $k$（$1 \le n, k \le 2 \cdot 10^5$）—— 数组 $p$ 和 $q$ 的长度。

每个测试用例的第二行包含 $n$ 个互不相同的整数 $p_0, p_1, \ldots, p_{n-1}$（$1 \le p_i \le 2n-1$，且每个 $p_i$ 均为奇数）—— 数组 $p$。

每个测试用例的第三行包含 $k$ 个互不相同的整数 $q_0, q_1, \ldots, q_{k-1}$（$0 \le q_i \lt k$）—— 数组 $q$。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$，且所有测试用例中 $k$ 的总和不超过 $2 \cdot 10^5$。

For each test case, output one integer: the number of inversions in array $a$ modulo $998\,244\,353$.

对于每个测试用例，输出一个整数：数组 $a$ 中逆序对的数量对 $998\,244\,353$ 取模的结果。

In the first test case, array $a$ is equal to $[3, 6, 5, 10, 1, 2]$. There are $9$ inversions in it: $(0, 4)$, $(0, 5)$, $(1, 2)$, $(1, 4)$, $(1, 5)$, $(2, 4)$, $(2, 5)$, $(3, 4)$, $(3, 5)$. Note that these are pairs $(i, j)$ such that $i \lt j$ and $a_i \gt a_j$.

In the second test case, array $a$ is equal to $[8, 4, 1, 2, 24, 12, 3, 6, 40, 20, 5, 10]$. There are $25$ inversions in it.

In the third test case, array $a$ is equal to $[1, 2, 4, 8, 16]$. There are no inversions in it.

在第一个测试用例中，数组 $a$ 等于 $[3, 6, 5, 10, 1, 2]$。其中包含 $9$ 个逆序对：$(0, 4)$、$(0, 5)$、$(1, 2)$、$(1, 4)$、$(1, 5)$、$(2, 4)$、$(2, 5)$、$(3, 4)$、$(3, 5)$。注意，这些是满足 $i \lt j$ 且 $a_i \gt a_j$ 的下标对 $(i, j)$。

在第二个测试用例中，数组 $a$ 等于 $[8, 4, 1, 2, 24, 12, 3, 6, 40, 20, 5, 10]$。其中包含 $25$ 个逆序对。

在第三个测试用例中，数组 $a$ 等于 $[1, 2, 4, 8, 16]$。其中不包含任何逆序对。