#include<bits/stdc++.h>
using namespace std;
const int N = 4e5 + 10, mod = 998244353;
int T, n, k, p[N], q, tr[N];
int lowbit(int x){return x&(-x);}
void add(int x, int sup){for(int i = x; i <= sup; i += lowbit(i)) tr[i] += 1;}
int query(int x){
	int res = 0;
	for(int i = x; i > 0; i -= lowbit(i)) res += tr[i];
	return res;
}
void init(){memset(tr,0,sizeof(tr));}
int abs(int x){return x < 0 ? -x : x;}
int del_sum(int st, int ed, int del){
	return 1ll * (st + ed) * (abs(st - ed) / del + 1) / 2 % mod;
}
void solve(){
	scanf("%d %d", &n, &k);
	for(int i = 1; i <= n; i += 1) scanf("%d", &p[i]);
	for(int i = 1; i <= k; i += 1) tr[i] = 0;
	int ans = 0;
	for(int i = 1; i <= k; i += 1){
		scanf("%d", &q);
		ans = (ans + query(k) - query(q + 1)) % mod;
		add(q + 1, k);
	}
	for(int i = 1; i <= 2 * n - 1; i += 1) tr[i] = 0;
	ans = 1ll * ans * n % mod;
	for(int i = 1; i <= n; i += 1){
		int res = 0;
		if(p[i] < 2 * n - 1)
			res = (query(2 * n - 1) - query(p[i])) * 1ll * k % mod;
		int l = 1, x = p[i] >> 1;
		while(x > 0 && l < k){
			res = (res + (query(2 * n - 1) - query(x)) * 1ll * (k - l)) % mod;
			l += 1;
			x >>= 1;
		}
		res = (res + query(2 * n - 1) * 1ll * del_sum(0, k - l, 1) % mod) % mod;
		l = 1, x = (p[i] << 1);
		while(x < 2 * n - 1 && l < k){
			res = (res + (query(2 * n - 1) - query(x)) * 1ll * (k - l)) % mod;
			l += 1;
			x <<= 1;
		}
		ans = (ans + res) % mod;
		add(p[i], 2 * n - 1);
	}
	printf("%d\n",ans);
}
int main(){
	//freopen("count.in","r",stdin);
	//freopen("count.out","w",stdout);
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}

Solution

首先我们把情况拆分一下：

• 对于 $i$ 相同的情形，事实上就是统计 {$q_j$} 的逆序对的数量，最终结果乘以 $n$ 然后加到答案里。
• 对于 $i$ 不同的情形，另行讨论。

考虑 $i$ 不同的情形，我们发掘一下性质：

• 因为只考虑不同的 $i$ 之间的逆序对，所以 {$q_j$} 的内部顺序是完全没有用处的。
• 不同的次数之间总是相差 $2$ 倍。

我们试着枚举一下：当前考虑到 $i$，要统计对于任意 $b<i$ ，$c$ 是 $[1,k]$ 之间的正整数，形如 $p_b*2^c$ 且比 $p_i*2^j$ 大的数字的总个数。

直接做当然是做不了一点，但是我们不妨再稍稍变换一下。

再枚举一个东西：假设确定了 $i和j$，然后枚举一个 $l$ ，表示要统计对于任意 $b<i$ 的，形如 $p_b*2^{j+l}$ 且比 $p_i*2^{j}$ 大的数的总个数。

问个问题：$l$ 的范围是多少？

你大概发现了，$l$ 最小不会小于 $log_2(p_i/N)$（其实是有可能超过的，但是超过的部分可以快速计算）。所以你枚举 $l$ 的总的时间复杂度是 $O(logN)$。

那么枚举了 $l$，接下来怎么统计呢？我们稍稍变一下形，就是要统计所有满足 $p_b>p_i*2^{-l}$ 的 $b$。这样我们从前往后扫一遍，边扫边维护一个树状数组，就可以在 $O(logN)$ 的时间内实现统计了。

然后我们想一想对于确定的 $l$，有多少个 $j$ 可以满足我们的条件呢？这个比较简单，显然是 $n - \left| l \right|$ 个。

总的时间复杂度是 $O(Nlog^2N)$。