Crate nekolib_doc::discussion::plane_sweep

平面走査。

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$ の昇順¹に点を処理する。 $a_{x_i} \xgets{\circ} f(i)$ で更新しつつ、$y\lt y_r$ について処理し終えたら $a_{x_l}\circ\dots\circ a_{x_r-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)。

ある $j\in[0\lldot n)$ に対して $f(j)\lt f(i)$ というのは $\min_{j\in[0\lldot n)} f(j)\lt f(i)$ と言い換えることができる。よって、$(S, \min, \infty)$ について上記の枠組みを適用することで解ける。

---

1. 必要に応じてソート順は変更してもよい。 ↩