k 値数列の転倒数 - noshi91のメモ

2019/04/20 実装の誤りなどを修正しました。
2021/02/18 説明を大幅に変更しました。

概要

qiita.com こちらの記事を読んで $2$ 値だけでなく一般の $k$ 値について拡張できそうだと思ったので、それを書きます。

$k$ 値転倒数が伴う群

\begin{align} G &= \mathbb{Z}^k \times \mathbb{Z} \\ (s_l, t_l) \cdot (s_r, t_r) &= (s, t) \\ s_i &= (s_l)_i + (s_r)_i \\ t &= t_l + t_r + \sum_{i > j} (s_l)_i (s_r)_j \end{align} このように定義すると、 $G$ は群になります。

\begin{align} S &= \lbrace 0, 1, \cdots, k - 1 \rbrace \end{align} とすると、自由モノイド $S^{\ast}$ が定義されます。

このとき、以下に定義する写像 $f$ は $S^{\ast}$ から $G$ へのモノイド準同型です。 \begin{align} f(a) &= (s, t) \\ s_i &= \# \lbrace j \mid a_j = i \rbrace \\ t &= \# \lbrace (i, j) \mid i < j, a_i > a_j \rbrace \end{align}

$G$ の演算は $\Theta(k)$ で行うことが出来るため、 $S^{\ast}$ を $f$ で $G$ に移して累積和を用いることで、 $k$ 種類の値からなる列の連続部分列の転倒数を計算するクエリを高速に処理することが出来ます。

$G$ 上の演算を行うアルゴリズム

積

\begin{align} \sum_{i > j} (s_l)_i (s_r)_j &= \sum_{i} (s_l)_i \sum_{j = 0}^{i - 1} (s_r)_j \end{align} であるため、 $\sum_{j = 0}^{i - 1} (s_r)_j$ の部分を累積で計算すれば時間計算量は $\Theta(k)$ となります。

単位元

単位元は $((0,0,\cdots,0), 0)$ です。

逆元

$s \in \mathbb{Z}^k$ に対して、 $(- s)_i = - s_i$ と定義します。 $(s, t) \in G$ の逆元 $(s, t)^{-1}$ は以下の関係式から計算できます。 \begin{align} (s, t)^{-1} &= (- s, - t^{\prime}) \\ ( (0, 0, \cdots, 0) , t^{\prime}) &= (s, t) \cdot (- s, 0) \end{align}

実装例

#include <array>

template <int K> struct k_inv {
  std::array<int, K> s;
  int t;

  k_inv() : s(), t(0) {}
  k_inv(int c) : s(), t(0) { s[c] = 1; }

  friend k_inv operator+(const k_inv &l, const k_inv &r) {
    k_inv ret;
    for (int i = 0; i != K; i += 1) {
      ret.s[i] = l.s[i] + r.s[i];
    }
    ret.t = l.t + r.t;
    int sum = 0;
    for (int i = 0; i != K; i += 1) {
      ret.t += l.s[i] * sum;
      sum += r.s[i];
    }
    return ret;
  }

  k_inv operator-() const {
    k_inv ret;
    for (int i = 0; i != K; i += 1) {
      ret.s[i] = (*this).s[i];
    }
    ret.t = -(ret + (*this)).t;
    return ret;
  }
};