Consider the pairs \((r_0,c_0)\) such that:

• \(1\le r_0\le H-h+1\)
• \(1\le c_0\le W-w+1\)
• There exists \((i,j)\) with \(0\le i < H,\ 0\le j < W\) such that cell \((r_0+i,c_0+j)\) is painted black.

Let \(X\) be the number of such pairs \((r_0,c_0)\). Then the sought answer is \((H-h+1)(W-w+1)-X\). From now on, we will consider how to find this \(X\).

When there is a cell \((R_k,C_k)\) painted black, cells \((r_0,c_0) \in [R_k-h+1,R_k] \times [C_k-w+1,C_k]\) satisfy the condition due to that black cell. Thus, it suffices to find the size of the union of these rectangular regions.

There are various ways to find the size of this union; here we will introduce a sweep line algorithm using a multiset>

When we sweep a scan-line extending in the \(r\)-axis direction, black cells appear within \([C_k-w+1,C_k]\) at \(r=R_k-h+1\), and disappear at \(r=R_k+1\). Thus, the size can be computed fast by maintaining the segments of black cells within the current sweep line in a multiset or a map, and accumulating the delta formed by those segments.

The problem can be answered correctly by appropriately implementing the algorithm. The complexity is \(O(N\log N)\).

Sample code (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;
}