另一个逆序对问题_信奥算法提高+/省选-

给定一个长度为 $n$ 的排列 $p_0,p_1,\ldots,p_{n-1}$ ，其中 $p$ 是 $1$ 到 $2n-1$ 之间所有奇数的一个排列；以及一个长度为 $k$ 的排列 $q_0,q_1,\ldots,q_{k-1}$ ，其中 $q$ 是 $0$ 到 $k-1$ 的一个排列。

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

对所有 $0\le i<n$ 和 $0\le j<k$ ，
$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]$ 。

注意：所有数组都从 $0$ 开始编号，并且数组 $a$ 的每个元素都是唯一的。

请你计算数组 $a$ 中的逆序对数量，对 $998244353$ 取模输出。

逆序对定义为一对下标 $(i,j)$ ，满足 $0\le i<j<nk$ 且 $a_i>a_j$ 。

第一行一个整数 $t$ （ $1\le t\le 10^4$ ），表示测试用例数量。

每个测试用例：

第一行两个整数 $n,k$ （ $1\le n,k\le 2\cdot 10^5$ ）
第二行 $n$ 个两两不同的奇数 $p_0,\ldots,p_{n-1}$ （ $1\le p_i\le 2n-1$ ），且 $p$ 是所有奇数的一个排列
第三行 $k$ 个两两不同的整数 $q_0,\ldots,q_{k-1}$ （ $0\le q_i<k$ ），且 $q$ 是 $0\sim k-1$ 的一个排列

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

对每个测试用例输出一行：数组 $a$ 的逆序对数量对 $998244353$ 取模的结果。

输入#1

4
3 2
3 5 1
0 1
3 4
1 3 5
3 2 0 1
1 5
1
0 1 2 3 4
8 3
5 1 7 11 15 3 9 13
2 0 1

输出#1

样例解释

输入里：
$p=[3,5,1]$ ， $q=[0,1]$ ，所以 $2^{q}=[2^0,2^1]=[1,2]$ 。

按定义 $a_{i\cdot k+j}=p_i\cdot 2^{q_j}$ （这里 $k=2$ ）：

所以 $a=[3,6,5,10,1,2]$ 。
逆序对就是找所有 $(i,j)$ （ $i<j$ ）且 $a_i>a_j$ 的对，数一数共有 $9$ 个，所以输出 $9$ 。

题目给出的第二组数据生成的数组是：
$a=[8,4,1,2,24,12,3,6,40,20,5,10]$ ，
其中逆序对个数为 $25$ ，所以输出 $25$ 。

第三组数据里 $p=[1]$ ， $q=[0,1,2,3,4]$ ，得到：
$a=[1,2,4,8,16]$ ，它是从小到大不下降的，因此没有逆序对，输出 $0$ 。