部分集合のサイズが \(2\) 以上という設定になっていますが、サイズが \(1\) 以下のときのバウンディングボックスの面積を \(0\) だと思うことにすると、全ての部分集合についての総和を求めても答えは変わりません。

各単位格子正方形について、バウンディングボックスに含まれる場合の数を計算し、その総和を求めれば良いです。

座標 \((X,Y)\) を左下、座標 \((X+1,Y+1)\) を右上とする正方形が \(S\) のバウンディングボックスに含まれるためには、以下の条件をすべて満たすことが必要十分条件です。

• \(x\) 座標が \(X\) 以下である点が \(1\) つ以上 \(S\) に含まれる
• \(x\) 座標が \(X+1\) 以上である点が \(1\) つ以上 \(S\) に含まれる
• \(y\) 座標が \(Y\) 以下である点が \(1\) つ以上 \(S\) に含まれる
• \(y\) 座標が \(Y+1\) 以上である点が \(1\) つ以上 \(S\) に含まれる

包除原理を用いると、以下の \(2\) 種類の値（とそれを回転させたもの）を計算できれば良いことになります。

• (a) \(x\) 座標が \(X\) 以下の点のみからなる集合の個数
• (b) \(x\) 座標が \(X\) 以下かつ \(y\) 座標が \(Y\) 以下の点のみからなる集合の個数

全ての単位格子正方形についての (a) の総和を求めることは簡単なので、(b) の総和を求める方法について考えます。

\(x\) 軸方向に平面走査を行うことを考えると、以下のようなクエリを高速に処理できるデータ構造を設計できれば良いです。

• \(y\) 座標が \(Y\) である点を追加する
• \(y\) 座標が \(Y\) 以下である点の個数を \(C_y\) としたときの \(\sum_{1 \le y \lt N} 2^{C_y}\) を求める

これは Lazy Segtree を用いるとクエリあたり \(O(\log N)\) で処理することが出来ます。

全体の計算量は \(O(N \log N)\) です。（コード）