AT_arc205_a 题解

题目大意

洛谷题面有点问题。建议看 AtCoder 的。

就是说给你一个字符矩阵，然后

Q

个询问，每次询问限定一个矩形区域，然后你可以找一个全是 . 的

2\times 2

的正方形，然后把其中任意一个改成 #。问你能这样操作多少次。要求

O(1)

或

O(\log)

回答每次询问。

考虑如何算对于每个询问的答案。

我们发现每个点至多当一次矩形内的左上角。所以直接枚举这个左上角，然后看以它为左上角的

2\times 2

的正方形是不是都是 .，然后把其中任意一个改成 # 的话就直接改左上角就行了。

也就是说，我们现在要统计对于在询问的矩形内的每个

2\times 2

的正方形有多少个是全为 . 的。

二维前缀和维护即可，注意边界。

AC Code

p

为前缀和数组。

p_{i, j}

表示

(1, 1)

到

(i, j)

的矩形内有多少个点做左上角的

2\times 2

的正方形内全是 .。

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

文章操作

相关推荐

评论

AT_arc205_a 题解