考察
B_i≥0なのでprefix sum PBは非減少で、区間minimumが固定されればsumB≤S-minという条件の相手endpoint範囲を二分探索できる。
区間[L,R]のA最小位置Mを選ぶと、Mを含む全subarrayのminimumはA_Mに固定され、残りは左右再帰へ重複なく分割できる。
採用する候補: range minimum位置でdivide-and-conquerし、Mを含むintervalは短い側のendpointだけ列挙して、長い側の有効範囲をPB上のbinary searchで数える。
minimumの変化を消し、各indexの列挙回数をsmall-side規則で対数回に抑えられる。
棄却する候補: 全(l,r)を列挙し、RMQとprefix sumで条件を定数/対数時間判定する。
interval自体が二次個あるためN≤2×10^5に間に合わない。
l≤M≤rなら条件はPB[r]-PB[l-1]≤S-A_Mとなり、l固定ではrのvalid集合がprefix、r固定ではlのvalid集合がsuffixになる。
[L,M]と[M,R]の短い方だけendpointを固定すると、再帰treeで各indexが短い側に入るたび担当区間sizeが少なくとも半減する。
最小位置で左右へ再帰すれば、各subarrayはその最小要素を代表とするnodeで一度だけcross intervalとして数えられる。
RMQまたはmin Cartesian treeで各区間の最小位置Mを得る。leftが短ければ各l∈[L,M]についてPB上で最大r∈[M,R]を探し、rightが短ければ各rについて最小lを探す。cross数を加え、[L,M-1],[M+1,R]へ再帰する。
典型の発動条件
minimum-pivot divide-and-conquer
発動条件: subarray costにminimum/maximumが含まれ、そのextremum位置を含む区間で値を固定できるとき。
range最小位置をpivotにcross intervalを数え、左右へ再帰する。
smaller-side enumeration
発動条件: divide-and-conquerのpivotが偏り得るが、cross pairの片側endpointだけ列挙できるとき。
短い側を走査して各要素の担当回数を対数に抑える。
monotone prefix sum binary search
発動条件: 非負列の区間和上限からendpointの境界を求めるとき。
非減少PBにlower/upper_boundしてvalid endpoint数を取る。
問題固有の要素
minimum pivotを含むintervalではmin項が定数A_Mになり、min+sumという混合条件が単なるprefix sum差の閾値へ変わる。
別の問題へ持ち帰る視点: extremumと加法量が混ざる区間条件では、extremumを固定する分割とprefix sum queryを組み合わせる。
正当性
各区間を最小位置で分けると、その位置を含む区間は現在節点、含まない区間は片側の子に一意に属する。Bの非負性から累積和は非減少なので、一端を固定すれば二分探索で条件を満たす他端の範囲を漏れなく数えられる。短い側を列挙しても各交差区間を落とさない。
実装上の注意
- S-A_M<0ならpivotを含むgood intervalは0で、unsigned underflowを避ける。
- B_i=0でPBが同値になるため、≤条件に合うupper_bound/lower_boundの種類と検索区間を正しく選ぶ。
復習の核
- 同じminimumが複数ある列でtie規約を固定し、あるsubarrayがどのpivot nodeで一度だけ数えられるかCartesian tree上で確認する。
計算量と制約
時間
O(N log²N)、短い側endpointは各要素O(log N)回、各二分探索O(log N)。
空間
O(N)、prefix・Cartesian tree・再帰stack。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N \leq 2 \times 10^5; 0 \leq S \leq 3 \times 10^{14}; 0 \leq A_i \leq 10^{14}; 0 \leq B_i \leq 10^9; All values in the input are integers.
出典