各 \(i\ (1 \leq i \leq M)\) について、\(S_i\) を以下のように定義します。

• \(A_j=B_i\) なる \(j\) の集合

するとこの問題は、以下のように言い換えられます。

以下の条件を満たすように数列 \(C=(C_1,C_2,\ldots,C_M)\) を構築する。このとき、\(C\) の最長増加部分列 (LIS) の長さの最大値はいくらか。

• すべての \(i\ (1 \leq i \leq M)\) について、\(C_i \in S_i\)

上記の問題は、既知の LIS を求めるアルゴリズムを少し変形することで解くことが可能です。計算量は問題文中にある特殊な制約を踏まえると、\(O(N \log N)\) となります。

実装例 (C++)