ABC372 D - Buildings

問題文

(0 オリジンで考える)

$0 \leq i < j < N$ で動くので、方針は以下のようになる

$(i, j)$ が条件を満たすかどうかを $0,1$ で表すとこのようになる。答えは各行を横に足していった和である。

j を固定する。$0 \leq i < j$ を満たす i に対して、$(i, j)$ が条件を満たすかどうかには単調性がある。

この単調性の切り替わりの部分は range max セグ木上の二分探索で見つけられる。

切り替わりの部分をもとに、答え(各 $i$ に対して条件を満たす $j$ の数の配列) を range add 遅延セグ木などで更新すれば良い。いもす法でもよい。