Plane Add

$lx \leq x \leq rx$ かつ $ly \leq y \leq ry$ を満たすマス $(x, y)$ に $ax + by + c$ を足すとき $a, b, c$ について分離して考えます.

• 一様な重み付きの長方形が $N$ 個あり, ある点を覆う長方形の重みの和を取得する.

上記の問題は取得クエリの回数を $Q$ として平面走査とBinary Indexed Treeで $O((N + Q) logN)$で行うことができ, 全体の計算量も同じになります.