ABC136 F. Enclosed Points - phyllo’s algorithm note

問題

2次元平面上にN個の点があり、各点のx座標、y座標はそれぞれ相異なる。
この点からなる集合Sについて、Sの空でない部分集合Tを考える。

f(T) := 各辺が座標軸と平行であってTの点をすべて含むような最小の長方形に含まれる点の個数

と定めるとき、Sの空でないすべての部分集合Tについてf(T)の和を求めよ。
答えは大きくなるため998244353で割ったあまりを求めよ。

制約

1 <= N <= 2*10^5
-10^9 <= x_i, y_i <= 10^9
x_i != x_j (i != j)
y_i != y_j (i != j)

解法

求める答えは「Σ_T f(T)」であるが、f(T)は「Σ_{点} 点はTに含まれるか」なので、「Σ_T Σ_{点} 点はTに含まれるか」と考えられる。

ここで、2つのΣは入れ替えてもよいことから、「Σ_{点} Σ_T 点はTに含まれるか」と考えると、各点について、その点を含むような部分集合の数を数え上げる問題と考えることができる。

ある点について、その点を含むような部分集合を考えると、その点から左上、左下、右上、右下にある点の数がわかれば、2^{その点の数}-1の部分集合が考えられる。
したがって、4方向について2^4通りの組み合わせ方の点を作れば良い。
(ただし、左上と右下、左下と右上の点を選んでいる部分集合の場合は、注目している点自身を含まないような集合でも点の数としてはカウントされるので、注目点のある/なしの分を考慮するため2倍にする)

ある点について、その点より左上、左下、右上、右下にある点の数を数える。
これは、BIT/FenwickTreeで左から右、下から上に点を入れていきながら数え上げられる。

(実装では、2^xは毎回計算すると遅くなってしまうため、事前計算しておく。)