[ABC045D] Snuke’s Coloring 题解

题目链接：[ABC045D] Snuke’s Coloring

题意：

给定一个 $H$ 行 $W$ 列的矩形，再给定矩形上 $N$ 个黑格子的坐标。

对于每个 $0\le i\le9$ ，求出有多少个 $3\times3$ 的子矩阵包含有恰好 $i$ 个黑格子。

$3 \leq H \leq 10^9, ~3 \leq W \leq 10^9,~0 \leq N \leq \min \left(10^5, H \times W\right)$

记 $f_{i,j}$ 表示点 $(i,j)$ 到点 $(i + 2, j + 2)$ 的矩阵的答案。

由于 $H,W$ 都很大，但 $N$ 很小，而每个黑点至多对周围的 $8$ 个格子产生贡献

那么我们只需要把所有涉及贡献的 $f$ 计算一下，显然其他的都是 $0$ ，并且可以 $\mathcal{O}(1)$ 计算。

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

int H,W,n,ans[N]; map<pii,int> mp;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> H >> W >> n;
    for(int i = 1, x, y; i <= n; i++)
    {
        cin >> x >> y;
        for(int tx = x - 2; tx <= x; tx++)
            for(int ty = y - 2; ty <= y; ty++)
                if(tx > 0 && tx < H - 1 && ty > 0 && ty < W - 1) ++mp[{tx, ty}];
    }
    for(auto && i : mp) ++ans[i.second];
    ans[0] += (H - 2) * (W - 2) - mp.size();
    for(int i = 0; i <= 9; i++) cout << ans[i] << '\n';
    return 0;
}