公式解説の手順により、長方形に覆われていないマスの個数に帰着します。

\(c\) 座標が小さい場合を考えます。「各 \(c\) 座標が長方形に覆われているか？」を持って \(r\) 座標の順に平面走査をすることを考えると、以下のクエリが解ければ良いことがわかります。

• 区間 \([l,r)\) に \(x\) を加算する。ただし、要素は常に非負になることが保証される。
• 全体で \(0\) となっている要素の総数を答える。

これは、区間加算および (区間の最小値, その個数) の遅延セグメント木を用いて処理できます。

一般の場合を考えます。区間の端点および \(c\) 座標の限界を座標圧縮します。それを \(X_1,X_2,\ldots,X_k\) としたとき、各区間 \([X_i,X_{i+1})\) に対応して、遅延セグメント木のノードに \((0,X_{i+1}-X_i)\) を持たせることで、 \(c\) 座標が小さい場合と同様に計算できます。

また、動的遅延セグメント木を使うこともできます。