概要

二値文字列の転倒数が従う群構造を紹介します。これによって範囲転倒数クエリが、累積和やSegment Treeで計算できます。Segment Treeでできます、という言及は今までに見たことがありましたが、累積和もできるという話は聞いたことがなかったのでまとめます。

二値文字列の転倒数とは、0と1からなる二値文字列 $s$ が与えられて、$s$ をソートするために必要な隣り合った0と1のswap数 $f(s)$ のことです。例えば、$s=101011$ を $001111$ にソートするためには、 $3$ 回のswapが必要なので、$f(101011) = 3$です。

長さ $n$ の二値文字列に対する転倒数は、ここで紹介する群構造によって、

$O(n)$で計算できます。
二値文字列 $s$ の任意の部分連続文字列 $s[l, r)$ の転倒数を計算するクエリは、前処理 $O(n)$ クエリ $O(1)$ で計算できます。
二値文字列 $s$ の一箇所を変更する更新クエリ、および任意の部分連続文字列 $s[l, r)$ の転倒数を計算するクエリを、ともに $O(\log n)$ で計算できます。

二値転倒数の代数構造

二値文字列 $s$ に含まれる(0の個数, 1の個数, 転倒数)を $g_s = (x_s, y_s, z_s)$とします。この時、二つの二値文字列 $s, t$ が与えられて $g_s, g_t$ が既知である場合、連結された二値文字列 $s+t$ の転倒数 $g_{s+t}$ は、二項演算子$\otimes$を用いて、$g_{s+t} = g_s \otimes g_t = (x_s + x_t, y_s + y_t, z_s + z_t + x_t y_s)$と表されます。第三成分は、$z_s, z_t$ 回のswapを行って、$00001111100000011111$のような形状にした後、真ん中の11111000000をswapする回数を足すので、このような形になっています。$g_{s+t}$のマージ則が定める二項演算は結合的であり、以下の性質を満たすため、この二項演算が定めるモノイドは群をなします。

単位元: $(0, 0, 0)$
逆元: $g^{-1} = (x, y, z)^{-1} = (-x, -y, -z + xy)$

利用可能なデータ構造

群をなす長さ $n$ データ列 $g_i\ (0 \le i < n)$ に対して、区間 $[l, r)$ のデータを二項演算によってかけあわせる効率的操作は、累積和によって可能です。具体的には、$g_i$を始めから $i$ 個掛けあわせたデータを $x_i$ とした時、$g_l \otimes g_{l+1} \otimes \cdots \otimes g_{r-1} = x_l^{-1} \otimes x_r$と簡便に計算できます。そのため、累積和によって構築 $O(n)$, クエリ $O(1)$ で二値転倒数が計算できました。

群は結合法則を満たすので、Segment Treeを利用することもできます。これによって、二値文字列の添字 $i$ を変更するクエリ、および区間 $[l, r)$ のデータを二項演算によってかけあわせる操作を、ともに $O(\log n)$ で計算することができます。

Verify

Dwacon 2019 Qual D - k-DMC では、各 $i$ について、区間 $[i, i+k)$ の二値転倒数を足し合わせる必要があります。静的二値文字列に対する転倒数は、前処理に $O(n)$ をかけることで、累積和で各 $i$ につき $O(1)$ で計算できるので、全体で $O(q n)$ の計算量で解くことができました。この群構造を利用することで、シンプルなコードで解答することができます（提出）。

一般の転倒数

置換の転倒数の計算は文字列の長さ $n$ に対して、BITやマージソートを用いて $O(n\log n)$ で計算できます。現在の最速は前原氏のスライドによると $O(n \sqrt{\log n})$ だそうです。