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)$。