転倒数の高速な求め方

まず、長さ \(N\) の数列の転倒数を \(O(N\log N)\) 時間で求める方法の復習をしてきましょう。

問題
長さ \(N\) の数列 \(X=(X_1,\ldots,X_N)\) の転倒数を \(O(N\log N)\) 時間で求めてください。

予め座標圧縮を行うことで、\(X_i\) は全て \(1\) 以上 \(N\) 以下の整数であるとしてよいです。
空の数列から始めて、\(i=1,\ldots,N\) の順に \(X_i\) を末尾に追加したときの転倒数の変化に注目する次のようなアルゴリズムを考えます。

• 長さ \(N\) の配列 \(\mathrm{cnt}\) を用意し、全ての要素を \(0\) で初期化する
• 答えを表す変数 \(\mathrm{ans}\) を用意し、\(0\) で初期化する。
• \(i=1,\ldots,N\) の順に以下を行う
  • \(\mathrm{ans} \leftarrow \mathrm{ans} + \sum_{x>X_i}\mathrm{cnt}[x]\)
  • \(\mathrm{cnt}[X_i] \leftarrow \mathrm{cnt}[X_i] +1\)
• \(\mathrm{ans}\) の値が求めるものである

このアルゴリズムは愚直に計算すると \(\sum_{x>X_i}\mathrm{cnt}[x]\) の計算に \(\Omega(N)\) 時間かかってしまうため、全体で \(\Omega(N^2)\) 時間かかってしまいます。しかし配列 \(\mathrm{cnt}\) に対する操作が「区間和を求める」「1箇所の値を更新する」のみであることから、segment tree や Fenwick tree で保持することによりこれらの操作を \(O(\log N)\) 時間で行え、全体で \(O(N\log N)\) 時間で上記のアルゴリズムを実行し転倒数を求めることができます。

元の問題

予め座標圧縮を行うことで、\(B_i\) は全て \(1\) 以上 \(N\) 以下の整数であるとしてよいです。

普通の数列で転倒数を求めるのと同様のアルゴリズムを考えます。「\(B_i\) を \(A_i\) 個追加する」という操作を「『\(B_i\) を \(1\) 個追加する』を \(A_i\) 回繰り返す」とみなすと、その過程で数列中にある \(B_i\) より大きな値の個数は変化しないことから、以下のアルゴリズムを得ます。

• 長さ \(N\) の配列 \(\mathrm{cnt}\) を用意し、全ての要素を \(0\) で初期化する
• 答えを表す変数 \(\mathrm{ans}\) を用意し、\(0\) で初期化する。
• \(i=1,\ldots,N\) の順に以下を行う
  • \(\mathrm{ans} \leftarrow \mathrm{ans} + A_i \times \sum_{x>B_i}\mathrm{cnt}[x]\)
  • \(\mathrm{cnt}[B_i] \leftarrow \mathrm{cnt}[B_i] +A_i\)
• \(\mathrm{ans}\) の値が求めるものである

このアルゴリズムは通常の転倒数を求めるアルゴリズムと同様に、segment tree や fenwick tree を用いることで \(O(N \log N)\) 時間で実行することができます。