問題

点集合 $S \subseteq \mathbb{Z} \times \mathbb{Z}$ を管理する。 $S = \emptyset$ から始めて、次のクエリを処理せよ。

  1. 区間 $[l, r)$ と整数 $k \ne 0$ が与えられる。線分 $\lbrace (x, y) \mid x \in [l, r) \wedge y = k \rbrace$ を $S$ に追加する。
  2. 区間 $[l, r)$ が与えられる。和 $\sum _ {x \in [l, r)} f_S(x)$ を答えよ。ただし $f_S(x)$ は $y_1 = \min \lbrace y \gt 0 \mid (x, y) \in S \rbrace$ と $y_2 = \min \lbrace y \lt 0 \mid (x, y) \in S \rbrace$ が共に存在するならば $y_1 - y_2$ でありそうでないならば $0$ と定義する。

考察過程

  • segment tree beats の例題らしい
  • 最小値がないなら $0$ になるのがなければ貼るだけぽいが、$0$ になる、どうすれば
  • $\infty$ の個数を別に持っておけば片側だけなら処理できる。でも両方なので
  • 両側 $\infty$ なら無視できる。片側だけ $\infty$ のやつは、上手く打ち消すようにしたいな
  • セグ木を $4$ 本持って、ある側にクエリ $[l, r), k$ が来たら反対側の $2$ 本目に chmin $[l, r), k$ して自分の側の $2$ 本目に chmin $[l, r), 0$ する感じでできそうでは？

解法

segment tree beats を $4$ 本持つ。$r$ の最大値 $N$ に対し $O((N + q) \log N)$。

具体的には区間 chmin + 区間和 (ただし $\infty$ の要素は無視する) の segment tree beats を $4$ 本で、以下のようになる:

  1. $a_x = \min \lbrace y \gt 0 \mid (x, y) \in S \rbrace$
  2. $b_x = \max \lbrace y \lt 0 \mid (x, y) \in S \rbrace$
    • $-1$ をかけておけば最小値に等しい
  3. $\exists y \gt 0. ~ (x, y) \in S$ なら $c_x = 0$ でそうでなければ $c_x = b_x$
    • $y \gt 0$ なクエリが来たら chmin $0$ をする
  4. $\exists y \lt 0. ~ (x, y) \in S$ なら $d_x = 0$ でそうでなければ $d_x = a_x$

リンク