考察
両視点から見える候補xはrより東でlから見えるものに一致する。可視性は中間ビルだけに依存し視点自身の高さは含まない。右から左へ進むと新たに中間へ入るビルが、それより低い東側候補だけを遮るので単調stackが使える。query(l,r)はlを挿入する前に答え、その後H_lより低い末尾をpopしてlを追加する。候補indexは単調なのでrを越す個数を二分探索できる。
典型の発動条件
可視要素の monotone stack
発動条件: 各位置から右を見た record high の列を多数 query したいとき。
走査方向を揃えて可視候補を stack で維持する。
問題固有の要素
二条件の一方が他方を含意することを証明すると、共通集合問題が一視点だけの query になる。
別の問題へ持ち帰る視点: query を左端でオフライン整列すると、位置ごとの可視 stack を一度ずつ構成できる。
正当性
x>rがlから見えるなら全中間高さはH_xより低い。rからxまでの中間位置はその部分集合なのでrからも見える。右からのstackは視点lの処理直前にlより東の可視候補を持つ。queryへ答えた後、H_lより低い末尾候補をpopしlをpushすると、次の視点l−1に対しlが遮る候補だけを除ける。各indexは一度だけpush/popされる。
実装上の注意
queryをstack更新前に処理する。pop条件はtopの高さ<H_l。高さは順列なので同値はない。r自身を含めずindex>rだけを数える。
復習の核
H=(3,1,2),(l,r)=(1,2)で答え1を確認し、視点高さを遮蔽物へ入れない。query→低いtop削除→l挿入の順を再現する。
計算量と制約
時間
O(N+Q log N)、stack構築は償却O(N)、各照会はindex列の二分探索。
空間
O(N+Q)。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 2 \leq N \leq 2 \times 10^5; 1 \leq Q \leq 2 \times 10^5; 1 \leq H_i \leq N; H_i\neq H_j\ (i\neq j); 1 \leq l_i < r_i \leq N; All input values are integers.
出典