AT_arc205_a 题解
Guizy
·
·
题解
::::info[题目大意]{open}
洛谷题面有点问题。建议看 AtCoder 的。
就是说给你一个字符矩阵，然后 Q 个询问，每次询问限定一个矩形区域，然后你可以找一个全是 . 的 2\times 2 的正方形，然后把其中任意一个改成 #。问你能这样操作多少次。要求 O(1) 或 O(\log) 回答每次询问。
::::
考虑如何算对于每个询问的答案。
我们发现每个点至多当一次矩形内的左上角。所以直接枚举这个左上角，然后看以它为左上角的 2\times 2 的正方形是不是都是 .，然后把其中任意一个改成 # 的话就直接改左上角就行了。
也就是说，我们现在要统计对于在询问的矩形内的每个 2\times 2 的正方形有多少个是全为 . 的。
二维前缀和维护即可，注意边界。
::::success[AC Code]
```cpp
#include<bits/stdc++.h>
#define int long long
#define r(x) for (int i = 1; i <= x; i++)
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define reb(i, a, b) for (int i = a; i >= b; i--)
using namespace std;
const int N = 550;
int n, q, p[N][N];
char s[N][N];
signed main()
{
cin.tie(0)->sync_with_stdio(0);
cin >> n >> q;
r(n) rep(j, 1, n) cin >> s[i][j];
r(n - 1) rep(j, 1, n - 1)
{
if (s[i][j] == '.' && s[i + 1][j] == '.' && s[i][j + 1] == '.' && s[i + 1][j + 1] == '.')
p[i][j]++;
p[i][j] += p[i][j - 1];
}
r(n - 1) rep(j, 1, n - 1) p[i][j] += p[i - 1][j];
for (int i = 1, u, d, l, r; i <= q; i++)
{
cin >> u >> d >> l >> r, d--, r--;
// 做左上角的点最多到 (d-1, r-1)
cout << p[d][r] - p[d][l - 1] - p[u - 1][r] + p[u - 1][l - 1] << "\n";
// 前缀和的容斥
}
return 0;
}
```
::::