前置き
を解いたのでメモ。前計算 $O(N\sqrt{N})$、クエリ $O(\sqrt N)$ で解きます。
問題
長さ $N$ の整数列 $A=(A _ 0, \ldots, A _ {N-1})$ が与えられる。以下のクエリを $Q$ 個処理せよ:
l r: $A$ の連続部分列 $A _ l A _ {l+1} \cdots A _ {r-1}$ の転倒数を計算する。
記号の定義
- 列 $A$ の転倒数を $I(A)$ と書く
- 列 $A,B$ に対して、$A _ i \gt B _ j$ なる $(i, j)$ の個数を $I(A,B)$ と書く
- 列 $A,B$ をこの順番に連結してできる列を $AB$ と書く
- 列 $A$ の連続部分列 $A _ l A _ {l + 1} \cdots A _ {r - 1}$ を $A _ {\lbrack l : r)}$ と書く
解法
区間クエリなので Segment Tree などの利用が思い浮かびますが、モノイドではあるものの演算を高速に計算することが難しいので、平方分割による解法を考えます。
列 $A$ を長さ $L = \Theta(\sqrt{N})$ のブロックで分割します。簡単のため $L \mid N$ を仮定して整数 $K = N / L= \Theta(\sqrt{N})$ を定めます。実装においても $\infty$ を末尾に $L$ 個未満だけ加えることで $L \mid N$ とできます。
さて、クエリ区間とブロックの関係は次の $2$ パターンが考えられます。
$I(XYZ)$ に関して、次が成り立ちます。
$$I(XYZ) = I(XY) + I(YZ) - I(Y) + I(X, Z). \tag{1}$$
タイプ 1 は式 $(1)$ を用いて計算し、タイプ 2 に関しては式 $(1)$ を変形した次の式 $(2)$ を用いて計算します。
$$I(Y) = I(XY) + I(YZ) - I(XYZ) + I(X,Z). \tag{2}$$
式 $(1),(2)$ の右辺に現れる $I(X,Z)$ 以外の項は $A$ のある連続部分列の転倒数となっています。ここで、これらの連続部分列の左端または右端の少なくとも一方がブロックの境界と一致していることが重要です。
なぜなら、左端がブロックの境界と一致するような連続部分列の個数は $\displaystyle \sum _ {i = 0} ^ {K - 1} (K - i) L = \Theta(K ^ 2 L) = \Theta(N\sqrt{N})$ 個しかないためです。同様にして、右端がブロックの境界と一致するような連続部分列の個数も $\Theta(N \sqrt{N})$ 個です。
従って、左端または右端がブロックの境界と一致するような合計 $\Theta(N \sqrt{N})$ 個の連続部分列に対する転倒数を全て前計算してしまえば、式 $(1), (2)$ の右辺のうち $I(X,Z)$ 以外の項は全て簡単に得ることができます。
ぱっと思いつく前計算の方針として、Binary Index Tree で各値の個数を管理しながら列を伸ばしていくという方法があります。しかし、この方法では前計算に $\Theta(N \sqrt{N} \log N)$ 時間掛かってしまうので、工夫する必要があります。
以下、この前計算を $O(N\sqrt{N})$ 時間で行う方法を説明します。
左端がブロックの境界と一致するような連続部分列の転倒数を前計算
まず、長さ $L$ 以下のものに関しては愚直に計算してしまっても $\Theta(L ^ 2 K) = \Theta(N\sqrt{N})$ 時間で済みます。当然、Binary Index Tree などを用いた高速化を行っても構いません。その場合は $\Theta(KL \log L) = \Theta(N \log N)$ 時間です。
長さが $L$ より大きく、左端がブロックの境界と一致するような連続部分列 $A _ {\lbrack i\cdot L : (i + 1)\cdot L + k)}\; (k\gt 0)$ の転倒数の計算を考えます。
$A _ {\lbrack i\cdot L : (i + 1)\cdot L + k)}$ を次のように $3$ つに分解します。
$$A _ {\lbrack i\cdot L : (i + 1)\cdot L + k)} = A _ {\lbrack i\cdot L : (i + 1)\cdot L)} A _ {\lbrack (i + 1)\cdot L : (i + 1)\cdot L + k - 1)} A _ {(i + 1)\cdot L + k - 1}.$$
$(1)$ は一般に成り立つのでこれを適用すると次のようになります。ただし、表記の簡単のため $\mathrm{invL}(i, l) := I(A _ {\lbrack i \cdot L: i \cdot L + l)})$ と定めました。
$$\begin{aligned} \mathrm{invL}(i, L + k) &= \mathrm{invL}(i, L + k - 1) + \mathrm{invL}(i+1, k) - \mathrm{invL}(i + 1, k - 1) \\ &+I(A _ {\lbrack i\cdot L : (i + 1)\cdot L)}, A _ {(i + 1)\cdot L + k - 1}). \end{aligned}$$
ここで、$c _ {i, k} := I(A _ {\lbrack i\cdot L : (i + 1)\cdot L)}, A _ {(i + 1)\cdot L + k - 1})$ は $A _ {i\cdot L + j} \gt A _ {(i + 1)\cdot L + k - 1}$ なる $0 \leq j \lt L$ の個数と一致します。従って、$A _ {\lbrack i\cdot L : (i + 1)\cdot L)}$ の要素を予めソートしておき、$A _ {(i + 1)\cdot L + k - 1}$ の値が大きい順に $k$ を走査して尺取り法を行うことで、全ての $k$ に対する $c _ {i, k}$ を計算できます。
この方法でネックとなるのは「$A _ {(i + 1)\cdot L + k - 1}$ の値が大きい順に $k$ を走査して」という部分で、ここで毎回ソートしてしまうと全体で $\Theta(N \sqrt{N} \log N)$ 時間掛かってしまいます。そこで、$i$ の降順に計算することにすれば、$i+1$ のときの $A _ {\lbrack (i + 1) \cdot L : KL)}$ のソート結果と $A _ {\lbrack i \cdot L : (i + 1)\cdot L)}$ のソート結果をマージソートの要領で併せることで、$A _ {\lbrack i \cdot L : KL)}$ のソート結果を $O(N)$ 時間で得られます。
以上より、すべての $c _ {i, k}$ の計算を全体 $O(N \sqrt{N})$ 時間でできたので、$\mathrm{invL}$ の計算も全体 $O(N \sqrt{N})$ 時間でできました。
右端がブロックの境界と一致するようなものに関しても同様にできるので、省略します。
さて、最後に残ったのは式 $(1), (2)$ における $I(X,Z)$ の計算です。ここで重要なのは、いずれの場合においても $X$ および $Z$ は $1$ つのブロックに包含されているということです。
即ち、各ブロックをソートした列を前計算しておき、$X$ を包含するブロックと $Z$ を包含するブロックの間で尺取り法を行うことで $I(X,Z)$ を $O(L) = O(\sqrt{N})$ 時間で計算できます。
なお、ソート列の前計算に関して、尺取り法において要素が $X$ や $Z$ に含まれるかの判定を行う必要があるので、添字の情報を付加した組 $(A _ i, i)$ をソートした列を覚えておく必要があることに注意します。
実装
$L \mid N$ となるように番兵を置くことで、左端/右端がブロック境界と一致するような連続部分列の転倒数の計算を共通化できて実装が楽になります。(右端の時はreverseして比較関数を逆転すればOK)
