考察
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.
出典