平面走査によって時間計算量 O(NlogN) で解くことができます。
まず、1次元の配列に対して以下の2種の操作を考えます。
- range_add(l,r,x): 区間 [l,r) の要素のそれぞれに x を足す。なお、この操作の後任意の要素が 0 以上であることが保証される。
- range_union(): 配列中の 0 より大きい要素の数を数える。
これは、要素に{区間の最小値, 区間中の最小値の数}を持つ遅延セグメントツリーを使うと実現することができます。
次に、本問題について考えます。
x 座標を小→大となるように見ていくと、以下のイベントが起こります。
- 現在見ている x 座標を xcur とする。
- 長方形の和集合のうち、xcur の部分を答えに足す。 ans=ans+range_union
- xcur がある長方形の lx と一致する場合、その長方形を追加する。 range_add(ly,ry,+1)
- xcur がある長方形の rx と一致する場合、その長方形を削除する。 range_add(ly,ry,−1)
これを全てのx座標について行うことで解けますが、O(max(NlogN,xmax−xmin)) となるため座標のスケールが大きいと間に合いません。
そこで、range_union の値が変化する x 座標のみに注目します。
range_union の値が変化する可能性があるのは長方形の追加、削除が行われたときのみであるため、
Δx:=x次に追加、削除が起きるタイミング−xcur
として、range_union×Δx を答えに足していくと全体で O(NlogN) で解くことができます。