ABC 248 Ex — Beautiful Subsequences

考察

P は permutation なので長さ len=R-L+1 の区間では max-min≥len-1=R-L であり、V_L=max(P_L…P_R)-min(P_L…P_R)-(R-L) は常に非負整数である。

固定した右端 R について条件を満たす左端数は V_L≤K の個数で、R を 1 ずつ進めたとき全 L の V_L は区間加算として更新できる。

採用する候補: 単調 stack で suffix max/min が変わる左端区間を求め、V_L に range add する。segment tree の各 node に小さい値と個数を K+1 段まで保持する。

K≤3 と V_L≥0 を使い、全左端の値を持ちながら条件内の小値だけを root から数えられる。

棄却する候補: 全 L,R を列挙し、区間 max/min を RMQ で取得して不等式を判定する。

区間が二次個あるため、各判定を定数または対数時間にしても N≤1.4×10^5 では間に合わない。

新しい P_R が suffix maximum を更新する左端範囲は単調 stack の pop 区間として互いにまとめられ、max の増分だけ V へ range add できる。minimum も対称に更新できる。

R の増加で -(R-L) は全 active L に -1 を加え、新しい L=R の値は 0 から始まる。これらも range add と point activation で表せる。

V は非負整数で root の最小値は active な singleton により 0 なので、小さい distinct 値を K+1 個と各個数だけ保持すれば、値≤K の個数を復元できる。

未使用 L を INF にした lazy segment tree を用意する。各 R で既存 active 範囲へ -1、新要素による suffix max/min の変化量を monotone stack が示す区間へ加算し、L=R を V=0 で有効化する。root の保持 pair のうち value≤K の count を答えへ足す。

典型の発動条件

monotone stack による suffix extrema 更新

発動条件: 右端を伸ばすたび、全左端に対する区間 max/min の変化をまとめて処理したいとき。

pop された extrema の担当左端区間へ、新値との差を range add する。

上位少数値を持つ lazy segment tree

発動条件: 全要素への区間加算があり、小さい固定閾値内の要素数だけが必要なとき。

各 node で K+1 個の最小 distinct 値と multiplicity を merge し、lazy を値へ一括加算する。

問題固有の要素

permutation の max-min は区間長-1 以上という下界により slack V が非負になり、K≤3 の条件は最小側 K+1 段だけを見る問題へ変わる。

別の問題へ持ち帰る視点: 小さい K の不等式数え上げでは、対象量の整数下界を示してから、閾値近傍の少数 rank だけを data structure に持てないか考える。

正当性

極値の変化は単調stackで列挙した範囲に限られ、長さ増分と合わせて各左端の評価値を正確に更新する。値は非負整数なので、K以下の異なる値は高々K+1個である。それより大きい値を要約から落としても、求める個数は失われない。

実装上の注意

  • node merge では左右の最大 2(K+1) 個の pair を値順にまとめ、同値の count を合算してから最小 K+1 distinct 値だけ残す。
  • 未有効な L の INF が range add で有効値へ落ちないよう十分大きくし、max stack と min stack の区間端を off-by-one なく対応させる。

復習の核

  • R を 1 回伸ばした小さな permutation で各 L の V を表にし、max/min stack の加算と全体 -1 後に segment tree の値が一致するか追跡する。

計算量と制約

時間

O((K+1)N log N)、K≤3、各nodeで最小K+1 distinct値をmerge。

空間

O((K+1)N)。

制約との対応

公式制約の確認範囲: Time limit: 6 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 1.4\times 10^5; P is a permutation of (1,\ldots,N).; 0 \leq K \leq 3; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Beautiful Subsequences の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 支配関係から不要な候補を単調stack・queueで削る

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: 単調stack・queueによる支配候補の削除

    補助タグ: 遅延評価する区間作用 区間monoid要約

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

    学習の位置

    体系上の位置: 支配関係から不要な候補を単調stack・queueで削る

    • 候補を捨てられる支配条件を証明し、各候補を高々一度だけ単調stack・queueから削除できる。

    先に読む単元:

    • 区間更新を要約へ作用させる — 結合的な区間要約を設計した後、更新作用の合成順と要約への適用を遅延評価する。
    • 区間monoid要約 — queryに十分な値と結合順・単位元を定義し、Segment Treeまたはprefix foldで動的区間要約を保つ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

    この解説で扱わないこと:

    • 全候補から極値を反復取得するheap・ordered set。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題