解题思路

题目要求计算数组 $a$ 的逆序对数，其中 $a_{i\cdot k+j}=p_i\cdot 2^{q_j}$。
将 $a$ 分成 $n$ 个块，每个块长度为 $k$。

块内逆序对：每个块内元素为 $p_i\cdot 2^{q_j}$，比较时 $p_i$ 为正常数，故大小关系完全由 $2^{q_j}$ 决定。由于 $q$ 是一个排列，块内逆序对数等于排列 $q$ 的逆序对数 $\operatorname{inv}(q)$。总共有 $n$ 个块，因此块内逆序对总数为 $n\cdot\operatorname{inv}(q)$。

块间逆序对：考虑两个不同块 $i<j$，需要统计满足 $p_i\cdot2^{q_{j_1}} > p_j\cdot2^{q_{j_2}}$ 的所有 $(j_1,j_2)$ 对。由于 $q$ 是 $0\ldots k-1$ 的排列，指数对 $(q_{j_1},q_{j_2})$ 取遍所有有序对，因此块间逆序对总数与 $q$ 的具体顺序无关。我们可以假设 $q=[0,1,\dots,k-1]$，此时每个块内元素为 $p_i,\ 2p_i,\ 4p_i,\ \dots,\ 2^{k-1}p_i$ 且严格递增（$p_i>0$）。这样块内逆序对为 $0$，原问题的答案变为
[ \text{ans}=n\cdot\operatorname{inv}(q)+\text{块间逆序对数量}. ]

现在问题转化为：给定序列 $p$（奇数，$1\ldots2n-1$ 的排列），对每个 $i$ 构造递增序列 $B_i=[p_i,2p_i,\dots,2^{k-1}p_i]$，求所有 $i<j$ 时 $B_i$ 与 $B_j$ 之间形成的逆序对总数（即所有 $x\in B_i,\ y\in B_j$ 且 $x>y$ 的数对）。

两个块之间的逆序对计数

固定两个不同的值 $x,y$（$x$ 来自左边块，$y$ 来自右边块），设 $m=k-1$。我们需要计算
[ F(x,y)=#{(a,b)\mid 0\le a,b\le m,\ x\cdot2^a > y\cdot2^b}. ]

因为 $x,y$ 是奇数，$x\cdot2^a$ 和 $y\cdot2^b$ 的大小关系可以通过比较 $x$ 与 $y$ 以及 $2^{a-b}$ 确定。

情况 1：$x<y$

令 $z=\left\lfloor\log_2\frac{y}{x}\right\rfloor$，则 $2^z x<y<2^{z+1}x$。
可以证明（通过归并排序的视角）： [ F(x,y)=\begin{cases} \frac{(m-z)(m-z+1)}{2}, & 0\le z\le m,\ 0, & z>m. \end{cases} ] 当 $z>m$ 时，$y>2^m x$，从而所有 $x\cdot2^a\le x\cdot2^m<y\le y\cdot2^b$，逆序对数为 $0$。
当 $z\le m$ 时，公式简化后为 $\binom{m-z+1}{2}$。

情况 2：$x>y$

令 $z=\left\lfloor\log_2\frac{x}{y}\right\rfloor$，则 $2^z y<x<2^{z+1}y$。
此时 [ F(x,y)=\begin{cases} (z+1)(m+1)+\sum_{i=z+1}^{m} i, & 0\le z\le m,\ (m+1)^2, & z>m. \end{cases} ] 当 $z\le m$ 时，求和为 $\frac{(m+z+1)(m-z)}{2}$，因此 [ F(x,y)=(z+1)(m+1)+\frac{(m+z+1)(m-z)}{2}. ] 当 $z>m$ 时，所有 $x\cdot2^a>y\cdot2^b$ 恒成立，逆序对数为 $(m+1)^2$。

快速计算所有块间逆序对

遍历 $p$ 数组（按原顺序），维护一个值域树状数组（BIT），记录左侧已经出现过的值。对于当前值 $y$，需要累加所有左侧 $x$ 与 $y$ 的 $F(x,y)$。

由于 $x$ 和 $y$ 的取值范围是 $1\ldots 2n-1$（奇数），而 $2n\le 4\times10^5$，我们可以直接以数值为下标。
注意到 $z$ 只需要枚举到 $\lfloor\log_2(2n)\rfloor+1$（约 $20$），因为更大的 $z$ 对应的区间会超出值域或 $F$ 值为常数。

对于 $x<y$：
枚举 $z=0,1,2,\dots$，区间 $I_z=(y/2^{z+1},\ y/2^z]$ 内的 $x$ 均满足 $2^z x<y<2^{z+1}x$。
对应的贡献为 $\binom{m-z+1}{2}$（若 $z\le m$，否则为 $0$）。
区间端点取整： [ L_z = \left\lfloor\frac{y}{2^{z+1}}\right\rfloor+1,\qquad R_z = \left\lfloor\frac{y-1}{2^z}\right\rfloor. ] 若 $L_z\le R_z$ 且 $R_z\ge 1$，则查询 BIT 中 $[L_z,R_z]$ 内 $x$ 的个数，乘以贡献累加。

对于 $x>y$：
枚举 $z=0,1,2,\dots$，区间 $J_z=(2^z y,\ 2^{z+1}y)$ 内的 $x$ 满足 $2^z y<x<2^{z+1}y$。
贡献 $D(z)$ 按上述公式计算。区间端点： [ L_z = 2^z y+1,\qquad R_z = 2^{z+1}y-1. ] 若 $L_z\le \text{maxVal}$，则查询 $[L_z,\min(R_z,\text{maxVal})]$ 内的 $x$ 个数，乘以 $D(z)$ 累加。

对于每个 $y$，$z$ 的枚举次数为 $O(\log(2n))$，每次 BIT 查询 $O(\log(2n))$，总复杂度 $O(n\log^2 n)$，可以通过（$n$ 总和 $2\times10^5$）。

最后答案加上块内逆序对 $n\cdot\operatorname{inv}(q)$ 并取模 $998244353$。

实现细节

• 使用 long long 计算中间结果，取模时注意正数。
• 树状数组大小设为 $2n+5$。
• 预处理 $2^z$ 的幂（1<<z）。
• 计算 $\operatorname{inv}(q)$ 可以用 BIT 或归并排序。
• 注意 $m=k-1$ 可能为 $0$，公式仍然适用。

代码框架

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353;

struct BIT {
    int n;
    vector<int> t;
    BIT(int _n) : n(_n), t(_n + 2, 0) {}
    void add(int i, int v) {
        for (; i <= n; i += i & -i) t[i] += v;
    }
    int sum(int i) {
        int s = 0;
        for (; i > 0; i -= i & -i) s += t[i];
        return s;
    }
    int range(int l, int r) {
        if (l > r) return 0;
        return sum(r) - sum(l - 1);
    }
};

ll inv_perm(vector<int>& q) {
    int k = q.size();
    BIT bit(k);
    ll inv = 0;
    for (int i = k - 1; i >= 0; --i) {
        inv += bit.sum(q[i] + 1);
        bit.add(q[i] + 1, 1);
    }
    return inv % MOD;
}

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    for (int i = 0; i < n; ++i) cin >> p[i];
    vector<int> q(k);
    for (int i = 0; i < k; ++i) cin >> q[i];
    
    // 块内逆序对
    ll inv_q = inv_perm(q);
    ll ans = (ll)n * inv_q % MOD;
    
    int m = k - 1;
    int maxVal = 2 * n - 1;
    BIT bit(maxVal);
    
    // 预处理 C(z) 和 D(z) 对于 z=0..20 (足够)
    const int L = 20;
    vector<ll> C(L + 2, 0), D(L + 2, 0);
    for (int z = 0; z <= L; ++z) {
        if (z <= m) {
            ll t = m - z;
            C[z] = t * (t + 1) / 2 % MOD;
            D[z] = ((ll)(z + 1) * (m + 1) + (ll)(m + z + 1) * (m - z) / 2) % MOD;
        } else {
            C[z] = 0;
            D[z] = (ll)(m + 1) * (m + 1) % MOD;
        }
    }
    
    // 遍历 p 数组
    for (int i = 0; i < n; ++i) {
        int y = p[i];
        // x < y
        for (int z = 0; ; ++z) {
            ll divisor = 1LL << (z + 1);
            ll Lz = y / divisor + 1;
            ll Rz = (y - 1) / (1LL << z);
            if (Lz > Rz || Rz < 1) break;
            if (Lz > maxVal) break;
            if (Rz > maxVal) Rz = maxVal;
            int cnt = bit.range(Lz, Rz);
            if (cnt) {
                ans = (ans + (ll)cnt * C[z]) % MOD;
            }
        }
        // x > y
        for (int z = 0; ; ++z) {
            ll Lz = (1LL << z) * y + 1;
            if (Lz > maxVal) break;
            ll Rz = (1LL << (z + 1)) * y - 1;
            if (Rz > maxVal) Rz = maxVal;
            int cnt = bit.range(Lz, Rz);
            if (cnt) {
                ans = (ans + (ll)cnt * D[z]) % MOD;
            }
        }
        bit.add(y, 1);
    }
    
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
}