[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;
}