Expand description
2D dynamic segment tree(implicit,交互 2 分木 + split 軸キャッシュ)
方針:
- 本体 API は
apply(rx, ry, act)とget_range(rx, ry) get(x, y)はget_range(x..x+1, y..y+1)のラッパー- 重要:ノードごとに「このノードはどちらの軸で split するか」を 1 度だけ決めて保持する
- クエリ依存の軸選択は「未決定ノードの初回 split 決定」にだけ使う
- これにより
left/rightが表す領域の意味が常に一意になり,正しさが保たれる
- split 不能(軸長 1)なら反転して試す,両方不能なら真の葉
ActedMonoidWithSize::e_with_size(len)のlenは「面積 area」とみなす