Official

B - Cross-free Matching Editorial by maspy

線分をソートしておき、\(a_1 \leq a_2 \leq \cdots\) が成り立つとしておきます。

◆ \(a_i\) がすべて相異なる場合

まずは簡単のため、 \(a_i\) がすべて相異なる場合について考えてみましょう。

このとき、線分 \(i, j\) を同時に選べることは、\(b_i < b_j\) が成り立つことと同値です。したがってこの場合には、本問題は 最長増加部分列（LIS） の長さを求める問題と等価になります。

最長増加部分列（LIS）問題
数列 \(A = (A_1, A_2, \ldots, A_N)\) に対して、その部分列であって（狭義 / 広義）単調増加なもののうち、最長であるものを求めよ。

LIS 長は、\(O(N\log N)\) 時間で求めることができます（後述）。

◆本問題の解法

本問題も、端点の座標が一致している場合をうまく扱うことで、LIS 長の計算に帰着することができます。

具体的には、線分をソートするときに、\(a_i = a_j\) の場合のルールを追加して、

  • \(a_i < a_j\) であるとき、線分 \(i\) は線分 \(j\) よりも小さいと定める。
  • \(a_i = a_j\) であるとき、さらに \(b_i > b_j\) であれば、線分 \(i\) は線分 \(j\) よりも小さいと定める。

とした順序によって線分をソートしておけばよいです。

ソート・LIS 長の計算はともに \(O(M\log M)\) 時間で行えるため、本問題は \(O(M\log M)\) 時間で解くことができます。

◆LIS 長の計算

\(2\) つの方法を挙げておきます。

  • 数列のある項までを見た時点での、末尾が \(x\) であるような増加部分列の最大長を \(\text{dp}[x]\) と定める。\(\text{dp}[x]\) の計算はセグメント木を用いて高速に行える。\(x\) の上限が大きい場合には、事前に座標圧縮をしておく。

  • 数列のある項までを見た時点での、長さ \(k\) の増加部分列の末尾として可能な最小値を \(\text{dp}[k]\) と定める。\(\text{dp}[k]\) の計算は二分探索により高速に行える。

◆解答例

posted:
last update: