https://miscalc.hatenablog.com/entry/2024/07/25/212618

概要

数列の各要素について「LIS に使われる可能性があるか、使われる場合 LIS の何番目か」を計算しておくといろいろ便利です。

前提

増加部分列は「値」というよりは「添字」をとってきたものと思うのが見通しがよいです。この記事では次のように、増加部分列を添字の列として定義します：

長さ $N$ の数列 $A_0, \dots, A _ {N-1}$ の増加部分列とは、添字の列 $i_0, \dots, i _ {\ell-1}$ であって、 $(0 \leq) \ i_0 \lt \dots \lt i _ {\ell-1} \ (\leq N-1)$ かつ $A_{i_0} \lt \dots \lt A _ {i _ {\ell-1}}$ を満たすもの。最長増加部分列 (LIS) とは、増加部分列のうち、長さ $\ell$ が最大のもの。

また、LIS 長を求める $2$ 種類の DP（二分探索、セグ木）は既知として進めます。

本題

まず、添字 $i$ が LIS に使われる場合、その LIS 上での位置は一意です（そうでないとしたら、より長い増加部分列がとれて矛盾）。

$\mathrm{idx}' [ i ] :=$ 列 $A_0, \dots, A_i$ の増加部分列のうち $i$ を含むものの長さの最大値 ${} - 1$

とすると、添字 $i$ が LIS に使われる場合の LIS 上での位置は $\mathrm{idx}' [ i ]$ に一致します。

ところで、LIS に絶対に使われない添字が存在することもあります。そこで、 $\mathrm{idx} [i ]$ を次のように定義します：

添字 $i$ が使われる LIS が存在する場合、 $\mathrm{idx} [i ] := \mathrm{idx}'[i]$ とする。
添字 $i$ が使われる LIS が存在しない場合、 $\mathrm{idx} [i ] := -1$ とする。

また、 $0 \leq j \leq \ell ^ * -1$ （ $\ell ^ *$ ：LIS 長）に対して $\mathrm{cand}[j]$ を、 $\mathrm{idx}[i] = j$ を満たす $i$ たち（つまり、LIS の $j$ 番目になりうる添字の候補）を昇順に並べた列とします。

この $\mathrm{idx}$ （と $\mathrm{cand}$ ）を求めて、LIS の性質に関するいろいろな問題に応用するのが今回やりたいことです。

$\mathrm{idx, cand}$ の性質

（記法の補足： $\mathrm{cand}[j][-1]$ は $\mathrm{cand}[j]$ の末尾要素を表すとします。）

LIS は必ず、 $\mathrm{cand}[j]$ それぞれから $1$ つずつ選んできてできる列のどれかです。ただし、そのような列が必ず LIS になっているわけではありません。
の中身は添字の昇順ですが、これは値の降順になっています。つまり、です。
- そうでないと仮定すると、LIS より長い増加部分列がとれてしまいます。
それぞれの先頭をとってきた列は LIS です。つまり、かつです。これは添字の辞書順最小、値の辞書順最大の LIS です。
- 添字が単調増加でないと仮定すると、ある $j$ が存在して $\mathrm{cand}[j][0] \geq \mathrm{cand}[j+1][0]$ となりますが、 $\mathrm{cand}[j][0] \lt \dots \lt \mathrm{cand}[j][-1]$ より $\mathrm{cand}[j+1][0]$ が使われる LIS が存在しないことになり、矛盾します。
- 値が単調増加でないと仮定すると、ある $j$ が存在して $A _ {\mathrm{cand}[j][0]} \geq A _ {\mathrm{cand}[j+1][0]}$ となりますが、 $A _ {\mathrm{cand}[j+1][0]} \geq \dots \geq A _ {\mathrm{cand}[j+1][-1]}$ より $\mathrm{cand}[j][0]$ が使われる LIS が存在しないことになり、矛盾します。
それぞれの末尾をとってきた列は LIS です。つまり、かつです。これは添字の辞書順最大、値の辞書順最小の LIS です。
- 増加部分列になっていることの証明は上と同様です。
上記の辞書順最小・最大の LIS の性質より、辞書順最小 [resp. 最大] の LIS は、列を反転したときの辞書順最大 [resp. 最小] になります。

$\mathrm{idx, cand}$ の求め方

$\mathrm{idx}'$ は LIS 長を求める DP と同時に求めることができます（二分探索・セグ木のどちらのバージョンでも OK、簡単なので略）。

さて、 $i$ を含む LIS が存在する（ $\mathrm{idx}[i] \neq -1$ である）ための必要十分条件は、次のいずれかを満たすことです：

$\mathrm{idx}'[i] = \ell ^ * - 1$
ある $i _ \mathrm{nxt}$ が存在して、 $i \lt i _ \mathrm{nxt}, A_i \lt A _ {i _ \mathrm{nxt}}, \mathrm{idx}'[i] + 1 = \mathrm{idx}[i _ \mathrm{nxt}]$

この事実を用いると、 $\mathrm{idx}'$ を利用して $\mathrm{idx}, \mathrm{cand}$ が $O(N)$ 時間で計算できます。 $i$ を後ろから見つつ、各 $j$ について「今まで見た $i _ \mathrm{nxt}$ のうち $\mathrm{idx}[i _ \mathrm{nxt}] = j$ である最小の（つまり、 $A _ {i _ \mathrm{nxt}}$ が最大の） $i _ \mathrm{nxt}$ 」を管理していけばよいです。（なお下の実装例では、これを管理するついでに $\mathrm{cand}$ を求めています。）

実装例

#include <algorithm>
#include <vector>
using namespace std;

// idx[i] := A の i 番目が LIS に使われ得るなら LIS の何番目か、使われ得ないなら -1
// cand[j] := LIS の j 番目になりうる A の要素の添字の配列 (添字の昇順、値の降順)
// cand[j].front() たちをとってきたもの: 添字の辞書順最小、値の辞書順最大の LIS
// cand[j].back()  たちをとってきたもの: 添字の辞書順最大、値の辞書順最小の LIS
struct LongestIncreasingSubsequence
{
  vector<int> idx;
  vector<vector<int>> cand;

  LongestIncreasingSubsequence() {}
  template <class T>
  LongestIncreasingSubsequence(const vector<T> &a) : idx(a.size())
  {
    // LIS 長を求める DP (ここで idx' を求める)
    const int n = a.size();
    vector<T> dp;
    for (int i = 0; i < n; i++)
    {
      auto it = lower_bound(dp.begin(), dp.end(), a[i]);
      idx[i] = it - dp.begin();
      if (it == dp.end())
        dp.emplace_back(a[i]);
      else
        *it = a[i];
    }

    // idx, cand を求める
    const int len = dp.size();
    cand.resize(len);
    for (int i = n - 1; i >= 0; i--)
    {
      if (idx[i] == len - 1 || (!cand[idx[i] + 1].empty() && a[i] < a[cand[idx[i] + 1].back()]))
        cand[idx[i]].emplace_back(i);
      else
        idx[i] = -1;
    }
    for (auto &candj : cand)
      reverse(candj.begin(), candj.end());
  }
};

問題例

ABC354 F - Useless for LIS

LIS に使われうる要素をすべて求めてください。

解答

$\mathrm{idx}$ の求め方の一部そのままです。

Library Checker - Longest Increasing Subsequence

LIS をひとつ復元してください。

解答

$\mathrm{cand}[j]$ それぞれの先頭・末尾をとってくることで、辞書順最小・最大が復元できます。

yukicoder No.1804 Intersection of LIS

LIS に必ず使われる要素をすべて求めてください。

解答

$\mathrm{cand}[j]$ の要素が唯一であるところが答えになります。解説は「辞書順最小と辞書順最大の共通部分」という書き方をしていますが、同じことです。

ABC360 G - Suitable Edit for LIS

整数列の $1$ 要素を他の整数に書き換えて、LIS 長を最大化してください。

解答

$A$ の先頭に $-\infty$ を、末尾に $\infty$ を付け加えておきます。LIS 長を $1$ 増やせるための必要十分条件は、ある添字 $i_1, i_2$ が存在して、 $\mathrm{idx}[i_1],\mathrm{idx}[i_2] \neq -1, \mathrm{idx}[i_1] + 1 = \mathrm{idx}[i_2], i_2 - i_1 \geq 2, A _ {i _ 2} - A _ {i _ 1} \geq 2$ となることです。

$i_1$ を全探索します。 $i_2$ としてありうるのは、 $j := \mathrm{idx}[i_1] + 1$ として $\mathrm{cand}[j]$ の要素のどれかです。 $\mathrm{cand}[j]$ 内では添字が昇順、値が降順になっていることに注目すると、 $i_2 = \mathrm{cand}[j][k]$ が条件を満たすような $k$ の集合は区間になります。よってこの区間を二分探索か尺取り法（ $i_1$ を $\mathrm{cand}$ に現れる順番で探索すれば尺取りできます）で求めればよいです。

yukicoder No.992 最長増加部分列の数え上げ

LIS の個数を（適当な mod のもとで）数え上げてください。（列は添字が異なれば区別します）

解答

DP をします。

$\mathrm{dp}(j, k) :=$ LIS の $[0, j)$ 番目を決めて、なおかつ $j-1$ 番目を $\mathrm{cand}[j-1][k]$ とするような方法の数

$\mathrm{cand}[j]$ 内では添字が昇順、値が降順になっていることに注目すると、配る DP で考えた場合は配る先が区間に、貰う DP で考えた場合は貰う先が区間になります。いずれにしても、この区間を二分探索か尺取り法で求めて累積和や imos 法を利用すればよいです。

答えが $\displaystyle \prod _ {j=0} ^ {\ell ^ * - 1} \left|\mathrm{cand}[j]\right|$ にはならないことには注意してください。

なお、もし「値が同じであれば添字が異なっても同じ列とみなす」という設定だった場合は結構面倒になりますが、部分列 DP のように考えればなんとかなります（略、後で追記するかも）。

「みんなのプロコン」本選 D - KthLIS

辞書順 $K$ 番目の LIS を求めてください。（リンク先の問題では値の辞書順・値が同じであれば同じものとみなすという設定ですが、以下では簡単のため添字の辞書順で考えます）

解答

数え上げの DP と同じことをします。ただし、その後に辞書順 $K$ 番目を求めたいので、後ろから DP します。

$\mathrm{dp}(j, k) :=$ LIS の $[j, \ell ^ *)$ 番目を決めて、なおかつ $j$ 番目を $\mathrm{cand}[j][k]$ とするような方法の数

このテーブルを求めた後は、テーブルの情報にしたがって答えを前から決めていくことができます。

ところで、テーブルに載せる数が非常に大きくなる場合があります。これは、 $K$ との min をとった値を計算することにすれば対処できます。モノイド $\min(x + y, K)$ の区間積だと考えて、セグ木に載せることで計算できます（追記：尺取りになることを考えると SWAG でもできますね）（ところで、このモノイドは逆元がないので累積和だとうまくいかない気がするのですが、解説には累積和と書いてあるのでできるのかもしれないです。ちゃんと読んでいないのでよくわかりません）。