Official

Ex - Beautiful Subsequences Editorial by nok0

\(K=0\) の場合

\(K=0\) の場合、以下の手法でこの問題に答えることができます。

遅延セグ木の \(L\) 番目の要素で、\((\mathrm{max}(P_L,\ldots,P_R) - \mathrm{min}(P_L,\ldots,P_R)) - (R -L )\) を管理します。

実はこの管理は区間加算のみを使って可能なので、区間加算 - 区間最小値とその個数の取得 を行う遅延セグ木を用い、 \(R\) を \(1,\ldots,N\) と動かすことによりこの問題に答えることができます。

遅延セグ木の更新方法

\(-(R-L)\) の部分は容易なので、以下では \(\mathrm{max}(P_L,\ldots,P_R)\) の部分をどのように区間加算によって管理するかを述べます。

ここで、stack を用いて最大値を管理するテクニックを応用することを考えます。

Stack で最大値を管理するテクニック

ある \(R\) を取ってきたとき、 \(\mathrm{max}(A_i, A_{i+1},\ldots,A_R)\) は \(i\) について単調非増加になっています。

\(R\) が \(1,2,\ldots,N\) と順に増加していくとき、 \(\mathrm{max}(A_i, A_{i+1},\ldots,A_R) \neq \mathrm{max}(A_{i+1}, A_{i+2},\ldots,A_R)\) なる \(i\) は、以下の手法を用いることにより stack で管理することができます。

  • 空の stack を用意する。
  • R が 増加するたびに、以下を行う。
    • stack が空でなく、stack の 先頭の値が \(A_R\) 未満である限り stack の先頭を pop する。
    • \(A_R\) を stack に push する。

\(A_1,A_2,\ldots,A_N\) はそれぞれ最大 \(1\) 回しか push されないので、このアルゴリズムは \(\mathrm{Ο}(N)\) で動作します。

上記の手法を用いることにより、この区間の最大値は \(X\) であるという情報が得られるので、区間加算で最大値を管理できます。(pop した場合、加算していた区間を取り消すように区間加算を行えばよいです。)

\(\mathrm{min}\) についても同様の手法で可能です。

計算量は \(\mathrm{O}(N\log N)\) です。

一般の場合

一般の場合も、遅延セグ木を少し変更すればよいです。最小値と個数を管理するのではなく、小さい値とその個数を順に \(K+1\) 個管理すれば良いです。

計算量は \(\mathrm{O}(NK\log N)\) もしくは\(\mathrm{O}(NK^2\log N)\)です。

補足（追記）

この問題は、 Permutation Tree と呼ばれるデータ構造の構築アルゴリズムを一部切り出したものです。 興味のある方は Permutation Tree についても調べてみてください。

文献

posted:
last update: