Union of Rectangles (large)

平面走査によって時間計算量 $O(NlogN)$ で解くことができます。

まず、1次元の配列に対して以下の2種の操作を考えます。

• $range\_add(l, r, x):$ 区間 $[l, r)$ の要素のそれぞれに $x$ を足す。なお、この操作の後任意の要素が $0$ 以上であることが保証される。
• $range\_union():$ 配列中の $0$ より大きい要素の数を数える。

これは、要素に{区間の最小値, 区間中の最小値の数}を持つ遅延セグメントツリーを使うと実現することができます。

次に、本問題について考えます。
$x$ 座標を小$→$大となるように見ていくと、以下のイベントが起こります。

• 現在見ている $x$ 座標を $x_{cur}$ とする。
• 長方形の和集合のうち、$x_{cur}$ の部分を答えに足す。 $ans = ans + range\_union$
• $x_{cur}$ がある長方形の $lx$ と一致する場合、その長方形を追加する。 $range\_add(ly, ry, + 1)$
• $x_{cur}$ がある長方形の $rx$ と一致する場合、その長方形を削除する。 $range\_add(ly, ry, - 1)$

これを全ての$x$座標について行うことで解けますが、$O(max(NlogN, x_{max} - x_{min}))$ となるため座標のスケールが大きいと間に合いません。

そこで、$range\_union$ の値が変化する $x$ 座標のみに注目します。
$range\_union$ の値が変化する可能性があるのは長方形の追加、削除が行われたときのみであるため、

$\varDelta x := x_{次に追加、削除が起きるタイミング} - x_{cur}$

として、$range\_union × \varDelta x$ を答えに足していくと全体で $O(NlogN)$ で解くことができます。