インタラクティブなコンテンツへのリンク

導入

LIS score の表を眺める

順列 $a = (2, 0, 3, 1)$ を例にとって考えます。$(i, j)$ 要素が $[i, j)$ の LIS の長さ (LIS score) に対応する行列を考えます。ただし、$i\ge j$ の場合の LIS score は $0$ ではなく $j - i \le 0$ と定義します。

$i$ 行 $j$ 列目のマスは区間 $[i, j)$ に対応し、そのマスに書かれた値が 該当の LIS score です。さて、隣り合うマスの値の差は高々 $1$ であることがわかります。 青の境界は差が $0$ であることを、赤の境界は $1$ であることを表します。 境界線が交差する点のうち、左下 2 本が赤、右上 2 本が青のものを緑の点でマークします。 上記の例では、各列の緑点の位置は $(\bot, 0, \bot, 2)$ 行目です。ただし $\bot$ は緑点がないことを意味します。

このとき、区間 $[i, j)$ の LIS score は $(j-i) - P^{\Sigma}_{i, j}$ と表すことができます。ここで $P^{\Sigma}_{i, j}$ は、上図において $i$ 行 $j$ 列目のマスより左下（紫の網掛け部分）にある緑の点の個数を意味します。 なお、$j-i$ は区間長に対応しています。 たとえば、上図の丸で囲まれた $0$ 行 $2$ 列目の値 $1$ に対して、区間 $[0, 2)$ の LIS score が $(2-0) - 1 = 1$ であることがわかります。

なお、緑の点は各行各列に高々 1 つしか現れません。

見慣れない図を眺める

さて、同じく順列 $a = (2, 0, 3, 1)$ に対して下記のような図を考えます。

上から $i$ 行目、左から $j$ 列目のマス $(i, j)$ に対して、$a_j = i$ のとき、赤の斜線を引きます。 その行の左に書かれた値と、その列の上に書かれた値が同じ部分に引かれることになります。

また、緑線は左端および上端から出発し、右端および下端に到着します。 この線は、以下のいずれかの条件でカーブします。

• 赤の斜線のあるマスに来たとき
• 一度交わったことのある別の緑線と、再度同じマスに来たとき

たとえば、$0$ 行目の左端から出発した緑線は、赤の斜線のあるマス $(0, 1)$ でカーブします。 また、$0$ 行目の左端と $1$ 行目の左端から出発した緑線は、マス $(1, 1)$ で一度交わった後マス $(2, 3)$ で再び遭遇し、各々避けるようにカーブします。

ここでは、こうして作った緑線のうち、上端から出発し下端に到着したもののみに着目します。 下端に到着した各々の緑線は、それぞれ上端の $(\bot, 0, \bot, 2)$ 列目から出発していたとわかります。ここで、$\bot$ は該当なし（左端から来た）を表すとします。 この $(\bot, 0, \bot, 2)$ が、最初の図における緑点の座標と一致していることがわかります。 このことは一般に成り立つので、この緑線の位置関係を求めれば十分となります。

解法の方針

分割統治法に基づいて解きます。長さ $n$ の順列に対して上記の図を考えたとき、斜線は上 $\lfloor n/2\rfloor$ 行には $\lfloor n/2\rfloor$ 本、下 $\lceil n/2\rceil$ 行には $\lceil n/2\rceil$ 本あることが順列の定義から言えます。 よって、（適切に座標圧縮などをした上で）$\lfloor n/2\rfloor$-サイズの問題と $\lceil n/2\rceil$-サイズの問題に分けて再帰的に解きます。 そうして解いた部分問題から、（座標圧縮を復元した上で）以下で紹介する演算 $\boxdot$ を駆使することで元問題の解を得られます。$\boxdot$ の計算に $O(n\log(n))$ 時間かかるため、全体で $O(n\log(n)^2)$ 時間となります。

演算の定義

定義：$\Sigma$ と $\square$

各行各列に高々 1 つの $1$ があり、残りは $0$ である行列 $P$ を考えます。 この行列の左下累積和、すなわち各境界から見た $1$ の個数に対応する行列を $P^{\Sigma}$ と書きます。たとえば次のようになります。 $$\left(\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{matrix}\right)^{\Sigma} = \left(\begin{matrix} 0 & 1 & 2 & 3 \\ 0 & 1 & 1 & 2 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{matrix}\right).$$ また、$\bullet^{\Sigma}$ の逆演算を $\bullet^{\square}$ と書きます。 $$\left(\begin{matrix} 0 & 1 & 2 & 3 \\ 0 & 1 & 1 & 2 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \end{matrix}\right)^{\square} = \left(\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{matrix}\right).$$

定義：$\odot$

さらに、$n\times n$ 行列 $A, B$ に対して演算 $A\odot B$ を導入します。 $n\times n$ 行列 $A\odot B$ の $(i, k)$ 成分は次のように表されます。 $$(A\odot B)_{i, k} = \min_{j\in[0, n)} (A_{i, j} + B_{j, k}).$$ ただし、ここでは便宜上、行列も 0-indexed ということにしておきます。 $\odot$ は、普通の行列積が $(+, \times)$ で定義されるのに対し、 $(\min, +)$ で定義された行列積と見ることができます。

定義：$\boxdot$

さて、$P, Q$ を各行各列に高々 1 つの $1$ があり、残りは $0$ である行列とします。これらに対し、$(P^{\Sigma}\odot Q^{\Sigma})^{\square}$ も各行各列に高々 1 つの $1$ があり、残りは $0$ である行列であることが示せます。 そこで、$\boxdot$ を以下のように定義します。 $$P\boxdot Q = (P^{\Sigma}\odot Q^{\Sigma})^{\square}.$$

順列の形（どこの行・列に $1$ があるかを表す）で与えられた $P, Q$ から、 $P\boxdot Q$ を（行列の演算を介さずに）順列の形で得るアルゴリズムがあります。 これも分割統治法に基づきます。 分割パートでは、上記のものと似たように順列を半々に分けて座標圧縮などをします。 統治パートはやや難しいので下記の論文を読みましょう。計算量は $O(n\log(n))$ 時間です。

元問題の解法の概要

さて、$\boxdot$ の紹介を終えたので、話を緑線や赤線のところに戻します。 ざっくりのイメージだけ書きます。順列 $P, Q$ が「上半分の緑線がどこから来てどこに行くか」 「下半分の緑線がどこから来てどこに行くか」に対応し、$P\boxdot Q$ は「それらを合わせたとき上半分のどこから来て下半分のどこに行くか」に対応します。 カーブの二つ目の条件「一度交わった緑線とは交わらないように動く」を $\boxdot$ がうまく処理しているらしいです。

さて、緑線の位置関係がわかったことで緑点の座標もわかりました。 なので、あとはクエリごとに「この座標より左下にある点の個数は？」というのを答えるだけです。 これは wavelet matrix などを使って求めることができます。

まとめ

まとめると、大枠は次のようになります。

• LIS score は、矩形領域の点の個数の数え上げに帰着される
• 所望の点は、緑線の位置関係と対応している
• 緑線の位置関係は、分割統治法で求められる
• この分割統治法の統治パートで、$\boxdot$ というのを使う
• $\boxdot$ も分割統治法で求められるが、この統治パートは非自明
• 矩形領域の点の数え上げは wavelet matrix で解ける

参考文献

• Tiskin, Alexander. "Semi-local string comparison: Algorithmic techniques and applications." Mathematics in Computer Science 1, no. 4 (2008): 571-603.
• arXiv

ジャッジ

• Library Checker :: Static Range LIS Query