当前位置：首页 > news >正文

F - Grid Clipping

news 2026/3/26 17:29:08

F - Grid Clipping

Problem Statement

There is a grid with $H$ rows and $W$ columns. The cell at the $r$-th row from the top and $c$-th column from the left is called cell $(r,c)$. Each cell is painted black or white: cell $(R_k,C_k)$ is black for $k=1,2,\ldots,N$, and the remaining $HW-N$ cells are white.

Find the number of rectangular regions in this grid with $h$ rows and $w$ columns such that all cells contained in them are painted white.

More formally, find the number of pairs of integers $(r_0, c_0)$ satisfying all of the following conditions:

$1\le r_0 \le H-h+1$
$1\le c_0 \le W-w+1$
Cell $(r_0+i,c_0+j)$ is painted white for all pairs of integers $(i,j)$ satisfying $0\le i< h,\ 0\le j< w$.

Constraints

$1\le h\le H\le 10^9$
$1\le w\le W\le 10^9$
$0\le N\le 2\times 10^5$
$1\le R_k\le H$
$1\le C_k\le W$
$(R_{k_1},C_{k_1}) \neq (R_{k_2},C_{k_2})$ $(k_1 \neq k_2)$
All input values are integers.

Input

The input is given from Standard Input in the following format:

$H$ $W$ $h$ $w$ $N$
$R_1$ $C_1$
$R_2$ $C_2$
$\vdots$
$R_N$ $C_N$

Output

Output the answer.

Sample Input 1

Sample Output 1

The two rectangular regions enclosed in red in the figure below satisfy all the conditions.

Sample Input 2

4 4 3 2 2
2 2
3 4

Sample Output 2

No rectangular region satisfies all the conditions.

Sample Input 3

449 449 3 14 0

Sample Output 3

Sample Input 4

31 9 5 7 10
14 8
8 4
18 8
12 1
8 5
9 6
18 1
14 7
5 6
26 7

Sample Output 4

解题思路

相较于直接找出不含黑色格子的 $h \times w$ 矩形，我们更容易确定包含至少一个黑色格子的 $h \times w$ 矩形。对于每一个黑色格子 $(R_i, C_i)$，所有包含它的 $h \times w$ 矩形的左上角坐标 $(r, c)$ 满足 $\max(1, R_i-h+1) \leq r \leq \min(H-h+1, R_i)$ 且 $\max(1, C_i-w+1) \leq c \leq \min(W-w+1, C_i)$。

这些左上角坐标 $(r, c)$ 共同构成一个矩形区域，我们称其为“不合法矩形”。以左上角坐标 $(r, c)$（其中 $1 \leq r \leq H - h + 1$，$1 \leq c \leq W - w + 1$）来唯一标识每一个可能的 $h \times w$ 矩形，那么每个不合法矩形对应的区域大小（即所覆盖的左上角个数），就表示包含该黑色格子的 $h \times w$ 矩形数量。

一个直观的想法是用所有 $h \times w$ 矩形的总数 $(H-h+1) \cdot (W-w+1)$ 减去各个不合法矩形的面积，来得到只含白色格子的 $h \times w$ 矩形数量。然而这样做存在问题：如果一个 $h \times w$ 矩形包含多个黑色格子，那么它的左上角 $(r, c)$ 会被多个不合法矩形同时覆盖，导致被重复减去多次。正确的做法应该是考虑容斥原理，即总矩形数减去所有不合法矩形并集的面积，这样每个包含至少一个黑色格子的矩形恰好被减去一次。

求若干矩形的并集面积可以用扫描线算法解决，可以参考【模板】扫描线。每个不合法矩形可以用左上角 $\left(\max(1, R_i-h+1), \max(1, C_i-w+1)\right)$ 和右下角 $\left(\min(H-h+1, R_i), \min(W-w+1, C_i)\right)$ 来表述。需要注意的是，题目中的面积是以格子为单位计算的，而标准的扫描线求面积通常处理连续坐标。为了统一，我们可以将右下角的坐标统一加 $1$，变为 $\left(\min(H-h+1, R_i)+1, \min(W-w+1, C_i)+1\right)$，这样矩形的面积就可以直接表示为横坐标差值与纵坐标差值的乘积，与扫描线的标准形式保持一致。另外由于纵坐标的取值范围很大，还需要进行离散化处理。

AC 代码如下，时间复杂度为 $O(n \log{n})$：

#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int N = 4e5 + 5;array<int, 4> p[N];
int xs[N * 2], sz;
struct Node {
    int l, r, mn, s, add;
}tr[N * 4];void pushup(int u) {
    tr[u].mn = min(tr[u << 1].mn, tr[u << 1 | 1].mn);
    tr[u].s = 0;
    if (tr[u << 1].mn == tr[u].mn) tr[u].s += tr[u << 1].s;
    if (tr[u << 1 | 1].mn == tr[u].mn) tr[u].s += tr[u << 1 | 1].s;
}void build(int u, int l, int r) {
    tr[u] = {l, r};
    if (l == r) {
        tr[u].s = xs[l + 1] - xs[l];
    }
    else {
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}void upd(int u, int c) {
    tr[u].mn += c;
    tr[u].add += c;
}void pushdown(int u) {
    if (tr[u].add) {
        upd(u << 1, tr[u].add);
        upd(u << 1 | 1, tr[u].add);
        tr[u].add = 0;
    }
}void modify(int u, int l, int r, int c) {
    if (tr[u].l >= l && tr[u].r <= r) {
        upd(u, c);
    }
    else {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, c);
        if (r >= mid + 1) modify(u << 1 | 1, l, r, c);
        pushup(u);
    }
}int find(int x) {
    return lower_bound(xs + 1, xs + sz + 1, x) - xs;
}int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, h, w, k;
    cin >> n >> m >> h >> w >> k;
    for (int i = 0; i < k; i++) {
        int x, y;
        cin >> x >> y;
        int l = max(1, y - w + 1), r = min(y, m - w + 1) + 1;
        p[i << 1] = {max(1, x - h + 1), l, r, 1};
        p[i << 1 | 1] = {min(x, n - h + 1) + 1, l, r, -1};
        xs[++sz] = l, xs[++sz] = r;
    }
    sort(xs + 1, xs + sz + 1);
    sz = unique(xs + 1, xs + sz + 1) - xs - 1;
    sort(p, p + 2 * k);
    if (sz) build(1, 1, sz - 1);
    LL ret = (n - h + 1ll) * (m - w + 1);
    for (int i = 0; i + 1 < k << 1; i++) {
        modify(1, find(p[i][1]), find(p[i][2]) - 1, p[i][3]);
        ret -= LL(p[i + 1][0] - p[i][0]) * (xs[sz] - xs[1] - !tr[1].mn * tr[1].s);
    }
    cout << ret;
    
    return 0;
}