まず、与えられる図形が長方形のみであり、さらに座標が十分小さい場合を考えてみましょう。この場合は二次元累積和を用いて各点がいくつの長方形に含まれるかを予め \(O(XY+N)\) で計算しておくことで、クエリあたり \(O(1)\) で解くことができます。

次に、図形が長方形とは限らない場合について考えてみます。この場合も、以下の図のようにして二次元累積和により \(O(XY+\sum M_i +Q)\) で求めることができます。

元の問題を考えてみましょう。座標のとりうる値が大きなため、二次元累積和を計算するために二次元配列を持つことができません。そこで、\(x\) 座標の小さい方から順に計算していくことにしましょう。

(イメージ図)

\(x\) を1つ進める際に必要な値の更新は(多角形の辺に沿った)区間加算なので、遅延セグメント木を用いることで高速に処理することができます。したがって、クエリ先読みと組み合わせることで、\(O((\sum M_i + Q)\log X)\) でこの問題を解くことができました。

なお、「区間加算を行うことになるので、遅延セグメント木を用いることで高速に処理することができます」と説明した部分は、y軸方向に累積和をとった後の値ではなく累積和をとる前の値を保持しておくことで、通常のセグメント木やBIT(Binary Index Tree)を用いて処理するもできます。

実装例(C言語/セグメント木)