AT_abc410_f [ABC410F] Balanced Rectangles 题解

## 前言
最近几场可以切 A~E 了，所以赛时没切掉 F。而且最最令人开心的是只 WA 了一个点的快感，可惜 Atcoder 不给部分分。

### 小细节
代码中可能出现的错误就放这里了，作者是用的数组和 `vector`，所以对使用 `map` 的家人们可能帮助不大。下文无特殊说明默认通过了样例（如果没过可以留言让我帮你调）：

- 样例 RE 了。
  - 可能是数组下标访问到负数了，需要在进行统计时初始值赋值为 $H \times W$，因为如果整个矩形都是您定义为 $-1$ 的那个字符，就会炸掉。
  - 可能是数组开小了，请分析您数组访问时是否越界。
  - 还有可能是其他某些地方您写错了，导致 RE，包括其他地方的数组访问。
- WA $\times\ 4$，可能是您存储需要还原的下标没有存 $H \times W$，您可能觉得之后反正都要将其赋值为 $1$，没有必要，但是别忘了这题有多测，下一次访问时不一定还是这个位置。
- WA $\times\ 2$，可能是您存储需要还原的下标有问题，比如一开始加进容器的是 $H$ 而不是 $H \times W$。
- WA $\times\ 1$，可能是您跟我一样在最后将统计数组清空时是用 `int k = v.size() - 1`，然后进行操作再 `pop_back()`，再将变量的值减一，并且判的是 `while (k)`，那么改成 `while (k + 1)` 即可。

如果都没有问题，那么只有您自己调试了。

## 解题思路
由于题目要求选出一个矩形，使得里面包含 `.` 的数量等于 `#` 的数量，所以我们可以将 `.` 视为 $1$，`#` 视为 $-1$，问题就转化为了求内部所有元素之和为 $0$ 的矩形数量。

求解的话需要枚举矩形左上角和右下角再进行求和，于是一个 $\mathcal{O}(H^3W^3)$ 的超朴素算法就出来了。再使用前缀和优化一下可以做到 $\mathcal{O}(H^2W^3)$。

但是注意到数据范围 $HW \leq 3 \times 10^5$，显然 T 到下辈子，因此可以分讨一下。
- $H \leq W$，那我们可以预处理每一行的前缀和，枚举的时候只需要枚举 $H$，相较于枚举 $W$ 减少了一点时间复杂度，为 $\mathcal{O}(H^3W^2)$。
- $H > W$，那我们可以预处理每一列的前缀和，同理，时间复杂度为 $\mathcal{O}(H^2W^3)$。

看这样子应该不可以优化了，但是给我们提供了一种思路，如果可以做到 $O(HW \times \min(H,W))$ 的话是可以通过的。先考虑 $H = 1, W = 3\times 10^5$ 的情况，复杂度为 $\mathcal{O}(H^2W)$，显然不会超时，只有当 $H = \sqrt{3\times 10^5}, W = \sqrt{3\times 10^5}$ 才会变成 $\mathcal{O}(n \sqrt{n})$ 的时间复杂度（$n = 3\times 10^5$），但是也不会超时，因此我们有了一个大概的方向。

这里才是这道题目最不容易想到的地方吧。注意我说的是“吧”。我们还是跟上面一样进行分讨。
- $H \leq W$，那么我们就枚举 $u, d$ 表示矩形的第一行位于网格的第 $u$ 行，最后一行位于网格的第 $d$ 行。然后前缀和出每一列中 $u\sim d$ 行的和。

接着就到了重点，首先我们知道对于前缀和数组 $sum$，想要算第 $l$ 项到第 $r$ 项的和，只需要计算 $sum_r - sum_{l - 1}$ 即可，那么我们只需要保证 $sum_r - sum_{l - 1} = 0$ 就能满足题意（即第 $u$ 行到第 $d$ 行中第 $l$ 列到第 $r$ 列的和为 $0$），移项可得 $sum_r = sum_{l - 1}$，由于我们不关心 $l - 1$ 的值是多少，因此只需要前面存在 $sum_k = sum_r$ 即可，因此我们只需要再枚举一个 $j$，表示第 $j$ 列，如果 $res$ 出现过，就将答案增加出现次数个 $1$，再 $res \to res + sum_j$，注意第一次出现 $res = 0$ 时你的答案没有增加，所以需要特殊处理。
- $H > W$，同理，是需要将上一种情况的行变成列，列变成行即可。

最坏时间复杂度约为 $\mathcal{O}(HW\sqrt{HW})$。别忘了多测要清空还有 $res$ 可能为负数导致数组越界哦。

都看这么久了，别忘了三连哦！

CODE：
```cpp
#include <bits/stdc++.h>
using namespace std;
#define int long long
string s[300010];
int sum[300010], cnt[600010];
vector<int> v;
signed main() {
	ios::sync_with_stdio(false);
	ios_base::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int n, m;
		cin >> n >> m;
		for (int i = 1; i <= n; i++) {
			cin >> s[i];
			s[i] = " " + s[i];
		}
		int ans = 0;
		if (n <= m) {
			for (int u = 1; u <= n; u++) {
				for (int j = 1; j <= m; j++) {
					sum[j] = 0;
				}
				for (int d = u; d <= n; d++) {
					for (int j = 1; j <= m; j++) {
						sum[j] += (s[d][j] == '.' ? 1 : -1);
					}
					cnt[n * m] = 1;
					v.push_back(n * m);
					int res = n * m;
					for (int j = 1; j <= m; j++) {
						res += sum[j];
						if (cnt[res]) {
							ans += cnt[res];
						}
						cnt[res]++;
						v.push_back(res);
					}
					for (int u : v) {
						cnt[u] = 0;
					}
					v.clear();
				}
			}
		} else {
			for (int l = 1; l <= m; l++) {
				for (int i = 1; i <= n; i++) {
					sum[i] = 0;
				}
				for (int r = l; r <= m; r++) {
					for (int i = 1; i <= n; i++) {
						sum[i] += (s[i][r] == '.' ? 1 : -1);
					}
					cnt[n * m] = 1;
					v.push_back(n * m);
					int res = n * m;
					for (int i = 1; i <= n; i++) {
						res += sum[i];
						if (cnt[res]) {
							ans += cnt[res];
						}
						cnt[res]++;
						v.push_back(res);
					}
					for (int u : v) {
						cnt[u] = 0;
					}
					v.clear();
				}
			}
		}
		cout << ans << "\n";
	}
	return 0;
}
```

正在渲染内容...