B - Two LIS Sum Editorial
by 
maspy
ヒント → https://atcoder.jp/contests/arc149/editorial/4868
[1] 問題の言い換え
隣接する \((A_i, B_i)\) と \((A_{i+1}, B_{i+1})\) を何度でもスワップできるということは，\(N\) 個の組 \((A_i, B_i)\) を自由な順に並べ替えられるということになります．したがって，本問は次のように言い換えることができます．
\(N\) 個の組 \((A_i, B_i)\) を自由に並べ替えたあと，\(2N\) 個の数 \((A_1, \ldots, A_N)\), \((B_1, \ldots, B_N)\) のうちいくつかに印をつける．この際，印をつけた \(A_i\) 全体，\(B_i\) 全体が単調増加になる必要がある．最大でいくつの印をつけられるかを求めよ．
[2] 最適解の構造
次を証明することができます：
最適解のうちで，すべての \(A_i\) に印がついているものが存在する．
このことを証明しましょう．まず，\(A_i, B_i\) のどちらにも印がついていないような \(i\) があれば，他の組 \((A_i, B_i)\) の位置関係を保ったまま \((A_i, B_i)\) を適切な位置に挿入したあと \(A_i\) に印をつけることで，印の個数を増やすことができます．
したがって最適解においては，任意の \(i\) に対して \(A_i\) または \(B_i\) に印がついていることが分かります．
同じ方法によって，すべての \(A_i\) に印がついている最適解が存在することを証明できます．\(A_i\) に印がついていない最適解がある場合，これを適切な位置に挿入したあと，\(B_i\) の印を削除して代わりに \(A_i\) に印をつけることで，全体での印の個数を保ったまま \(A_i\) についている印の個数を増やすことができます．
したがって，最適解をひとつとり，この操作を可能な限り繰り返せば，すべての \(A_i\) に印がついているような最適解が得られます．
[3] 本問の解法
結局本問題の答は次のように計算することができます．
- \(N\) 個の組 \((A_i, B_i)\) を，\(A_i\) が昇順に並ぶようにソートする．
- このときの \(\mathrm{LIS}(A)+\mathrm{LIS}(B)=N+\mathrm{LIS}(B)\) が答である．
\(\mathrm{LIS}(B)\) は \(O(N\log N)\) 時間で計算できるので，本問題は \(O(N\log N)\) 時間で解くことができます．
LIS の計算について
\(2\) つの方法を挙げておきます．
数列のある項までを見た時点での，末尾が \(x\) であるような増加部分列の最大長を \(\text{dp}[x]\) と定める．\(\text{dp}[x]\) の計算はセグメント木を用いて高速に行える．\(x\) の上限が大きい場合には，事前に座標圧縮をしておく．
数列のある項までを見た時点での，長さ \(k\) の増加部分列の末尾として可能な最小値を \(\text{dp}[k]\) と定める．\(\text{dp}[k]\) の計算は二分探索により高速に行える．
解答例
posted:
last update: