JOI春合宿2019 2-1 Two Antennas 解説
解説
小課題から消化していく．
小課題 1
愚直に実装すればよい．$O(N^2Q)$ で解ける．
小課題 2
すべてのペアについて探索すると，グリッド上での長方形内の最大を求める問題になる．2次元セグ木を書くと，$O(N^2+Q\log^2N)$ で解ける．
小課題 3
ペアを構成する左側のアンテナについて，「ここからはこのアンテナの電波が届き，ここからは届かない」というように，左側のアンテナを enable/disable するクエリをアンテナの右側に追加しておくことを考える．こうすると，一点変更区間取得の Range Minimum/Maximum Queries を捌けばいいことになり，セグ木で解ける．
満点
小課題 3 の方法だと，区間クエリが複数来た場合に対応できない．次のような操作が可能なセグ木で，区間に対するクエリがセグ木で捌けるようにする．
- $B_i$ を enable/disable する．
- 区間 $[L, R)$ に対し，chmin/chmax(A_i, x - B_i) する．
- 区間 $[L, R)$ に対し，min/max(A_i) を求める．
このようなデータ構造を，セグ木のような形で実装して，クエリを先読みして右側から処理していけば，$O((N+Q)\log N)$ で満点が取れる．
感想
バグりまくって，online-judge-tools でバグ取りをした． これ本番で出たら通せる気がしない
