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