ABC 354 F — Useless for LIS

考察

A_i を含む増加部分列は、i で終わる左側最長長 l_i と i で始まる右側最長長 r_i を A_i で接続して長さ l_i+r_i−1 にできる。全体 LIS 長を L とすると A_i が少なくとも一つの LIS に含まれる必要十分条件は l_i+r_i−1=L である。l_i は A_i 未満の値で終わる過去 DP 最大+1、r_i は右側で A_i より大きい値から同様に求まり、strict 不等号を守る。l_i と r_i を達成する subsequence は index i だけを共有し、値も左<A_i<右なので連結して実際の LIS 候補になる。

採用する候補: 前向き LIS DP で l_i、反転・符号反転した同型 DP で r_i を求め、長さ条件で各 index を判定する。

各方向 O(N log N) で、要素ごとの「左から何番目・右から何番目になれるか」を完全に捉える。

棄却する候補: LIS を一本だけ復元し、その中の index だけを答える。

LIS が複数ある場合、復元した一本に無いが別の LIS に含まれる要素を取り逃す。

値を座標圧縮する。左から Fenwick/segment tree の prefix max で l_i=1+max(rank<A_i) を求める。右から suffix max で r_i=1+max(rank>A_i) を求める。L=max l_i とし、l_i+r_i−1=L の index を昇順出力する。

典型の発動条件

前後 DP の一点接続

発動条件: ある要素を必ず通る最適部分列・path の長さを全点で判定するとき。

始点側最適値と終点側最適値を重複一点ぶん引いて足す。

LIS の range maximum DP

発動条件: 各要素で終わる strict increasing subsequence 長を全 index で欲しいとき。

座標圧縮値未満の最大を query し、現在rankへ chmaxする。

問題固有の要素

「ある LIS に含まれる」と「復元した LIS に含まれる」を区別し、存在判定を左右の最適値の等式へ変える。

別の問題へ持ち帰る視点: 最適解への要素参加可能性は、その要素を境にした prefix/suffix optimum の和で判定できることが多い。

正当性

iを含む増加部分列は左からiへ終わる最長とiから右へ始まる最長を結べるため最大長l_i+r_i−1。左右はi以外で重ならず厳密値条件もiを境に成立する。全LIS長Lとの等号がLISに含まれる必要十分条件。

実装上の注意

  • strict LIS なので前向きは rank 未満、後向きは rank より大きい範囲を使う。test case ごとに tree を初期化し総 N 制約を活かす。

復習の核

  • 一本復元で済まない理由を重複値・分岐する LIS 例で確認する。左右 DP の strict range を左右対称に実装する。

計算量と制約

時間

列長N。圧縮と左右max構造で O(N log N)。

空間

左右長と圧縮値、treeで O(N)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq T \leq 2 \times 10^5; 1 \leq N \leq 2 \times 10^5; 1 \leq A_i \leq 10^9; The sum of N across all test cases is at most 2 \times 10^5.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Useless for LIS の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 値域集約による部分列DP

主題
  • 値域集約による部分列DP: 末尾の値ごとに最良状態を持ち、許される直前値の区間を集約して部分列DPの遷移を高速化する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: 値域集約による部分列DP

    補助タグ: 座標・値の順序保存圧縮 区間monoid要約

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: 値域集約による部分列DP

    • 末尾の値ごとに最良状態を持ち、許される直前値の区間を集約して部分列DPの遷移を高速化する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    • 疎なkeyの順序を保ってdense indexへ圧縮する — 保持すべき疎な座標をsort-uniqueして順序・等値性を添字へ写す。距離・時間差・区間長も使う場合は元座標と間隔を併せて保存する。
    • 列・subsequence DP — DPの最小十分状態で得た考え方と実装を再利用し、列・subsequence DPの発動条件・正当化・境界を重複なく学ぶ。
    • 区間monoid要約 — queryに十分な値と結合順・単位元を定義し、Segment Treeまたはprefix foldで動的区間要約を保つ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題