Help us understand the problem. What is going on with this article?

二値文字列の転倒数が従う群構造

概要

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

二値文字列の転倒数とは、01からなる二値文字列 $s$ が与えられて、$s$ をソートするために必要な隣り合った01の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})$ だそうです。

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away