最終的な \(x\) の長さは \(10^{10}\) 程度になりえます。よって、長さ \(n\) の数列の転倒数を \(O(n \log n)\) で求めるアルゴリズムをそのまま適用することはできません。 \(a_{i,j} \leq 20\) と数列の要素の種類数がこの問題における重要な制約です。

数列 \(a\) の転倒数を \(\mathrm{inv}(a)\) とします。 また、数列 \(a\) における \(v\) の出現回数を \(\mathrm{cnt}(a,v)\) とします。

数列 \(x\) の末尾に \(a_i\) を連結した数列の転倒数を求めることを考えます。 これは \(\mathrm{inv}(x) + \mathrm{inv}(a_i) + \sum_{u=1}^{20}\sum_{v=1}^{u-1} \mathrm{cnt}(x,u) \mathrm{cnt}(a,v)\) となります。

適切に実装を行うと、数列の要素の種類数を \(X\) として \(O(\sum_{i=1}^{K}(n_i \log n_i) + QX)\) で最終的な \(x\) の転倒数を求めることができます。