AT_abc410_f [ABC410F] Balanced Rectangles 题解

Snowflake_Fairy · 2025-06-15 12:00:17 · 题解

前言

最近几场可以切 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 到下辈子，因此可以分讨一下。

看这样子应该不可以优化了，但是给我们提供了一种思路，如果可以做到 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），但是也不会超时，因此我们有了一个大概的方向。

这里才是这道题目最不容易想到的地方吧。注意我说的是“吧”。我们还是跟上面一样进行分讨。

• 接着就到了重点，首先我们知道对于前缀和数组 $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$ 时你的答案没有增加，所以需要特殊处理。

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

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

CODE：

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