以下の条件を全て満たす \((r_0,c_0)\) を考えます。

• \(1\le r_0\le H-h+1\)
• \(1\le c_0\le W-w+1\)
• \(0\le i < H,\ 0\le j < W\) を満たす整数の組 \((i,j)\) であって、マス \((r_0+i,c_0+j)\) が黒で塗られているようなものが存在する

これらの条件を全て満たす \((r_0,c_0)\) の個数を \(X\) とすると、求める答えは \((H-h+1)(W-w+1)-X\) となります。以降はこの \(X\) を求めることを考えます。

ある黒で塗られたマス \((R_k,C_k)\) があったとき、それにより条件を満たすマスは \((r_0,c_0) \in [R_k-h+1,R_k] \times [C_k-w+1,C_k]\) となります。したがって、これらの長方形領域の和集合の大きさを計算できれば良いです。

この長方形領域の和集合の大きさを求める方法は様々なものがありますが、ここでは multiset を用いた平面走査を紹介します。

各長方形領域は \(r\) 軸を走査していくと \(r=R_k-h+1\) で \([C_k-w+1,C_k]\) に黒マスが表れ \(r=R_k+1\) でそれが消えるという形で捉えることができます。したがって、 \(r\) の昇順に今どの区間に黒マスがあるのかを multiset や map で保持し、それらがなす面積を差分を考えることで高速に計算することができます。

以上を適切に実装することでこの問題に正答することができます。計算量は \(O(N\log N)\) です。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

	long H, W, h, w, n;
	cin >> H >> W >> h >> w >> n;
	vector<tuple<long, long, bool>> g;
	g.reserve(2 * n);
	for (int i = 0; i < n; i++) {
		long r, c;
		cin >> r >> c;
		r--, c--;
		g.push_back({r - h + 1, c - w + 1, true});
		g.push_back({r + 1, c - w + 1, false});
	}
	sort(g.begin(), g.end());
	multiset<long> s;
	s.insert(-w);
	s.insert(W - w + 1);
	long ans = (H - h + 1) * (W - w + 1);
	auto gap = [&](long l, long r) { return max(0L, r - l - w); };
	const long Y = W - w + 1;
	const long X = H - h + 1;
	long good = Y;
	auto add = [&](long x) {
		auto it = s.lower_bound(x);
		long r = *it, l = *prev(it);
		good += gap(l, x) + gap(x, r) - gap(l, r);
		s.insert(x);
	};
	auto del = [&](long x) {
		auto it = s.find(x);
		long r = *next(it), l = *prev(it);
		good -= gap(l, x) + gap(x, r) - gap(l, r);
		s.erase(it);
	};
	long pre = 0;
	int i = 0;
	while (i < 2 * n) {
		const long x = get<0>(g[i]);
		const long nx = min(x, X);
		if (pre < nx) {
			ans -= (nx - pre) * (Y - good);
			pre = nx;
		}
		while (i < 2 * n && get<0>(g[i]) == x) {
			auto [r, c, in] = g[i];
			if (in) add(c);
			else del(c);
			i++;
		}
	}
	if (pre < X) ans -= (X - pre) * (Y - good);
	cout << ans << endl;
}