plane_sweep/

lib.rs

//! 平面走査。
//!
//! ## Idea
//!
//! 可換モノイド $`(S, \circ, e)`$ がある。
//! $`n`$ 個の相異なる点 $`(y_i, x_i)`$ と $`f(i) \in S`$ が与えられる。
//! 必要に応じて座標圧縮などを行うことで、$`x_i\in[0\lldot n)`$ とする。
//! このとき、$`y\in[-\infty\lldot y_r)`$ かつ $`x\in[x_l\lldot x_r)`$ なる点たちにおける
//! $`\circ`$ での fold を高速に求めたい。
//!
//! $`a = (a_0, a_1, \dots, a_{n-1})`$ で初期化し、$`y`$ の昇順[^1]に点を処理する。
//! $`a_{x_i} \xgets{\circ} f(i)`$ で更新しつつ、$`y\lt y_r`$ について処理し終えたら
//! $`a_{x_l}\circ\dots\circ a_{x_r-1}`$ を求めればよい。
//!
//! [^1]: 必要に応じてソート順は変更してもよい。
//!
//! $`(S, \circ)`$ が逆元を持つ状況では、適切に点を追加することで $`y\in[y_l\lldot y_r)`$
//! での fold を求めることもできる。
//!
//! ## Applications
//!
//! 点 $`(y_i, x_i)`$ に対し、$`y_j \lt y_i`$ かつ $`x_j \lt x_i`$ なる点 $`(y_j, x_j)`$ であって
//! $`f(j) \lt f(i)`$ なるものが存在するか？という問題を考える ([ABC 309 F])。
//!
//! [ABC 309 F]: https://atcoder.jp/contests/abc309/tasks/abc309_f
//!
//! ある $`j\in[0\lldot n)`$ に対して $`f(j)\lt f(i)`$ というのは $`\min_{j\in[0\lldot n)} f(j)\lt f(i)`$
//! と言い換えることができる。よって、$`(S, \min, \infty)`$ について上記の枠組みを適用することで解ける。