算法竞赛模板

Balanced Rectangles

Problem Statement

You are given an $H \times W$ grid, where each cell contains # or ..
The information about the symbols written in each cell is given as $H$ strings $S_1,S_2,\dots,S_H$ of length $W$, where the cell in the $i$-th row from the top and $j$-th column from the left contains the same symbol as the $j$-th character of $S_i$.
Find the number of rectangular regions in this grid that satisfy all of the following conditions:

• The number of cells containing # and the number of cells containing . in the rectangular region are equal.

Formally, find the number of quadruples of integers $(u,d,l,r)$ that satisfy all of the following conditions:

• $1 \le u \le d \le H$
• $1 \le l \le r \le W$
• When extracting the part of the grid from the $u$-th through $d$-th rows from the top and from the $l$-th through $r$-th columns from the left, the number of cells containing # and the number of cells containing . in the extracted part are equal.

You are given $T$ test cases. Find the answer for each of them.

一维就是一个简单的 前缀和 + 桶计数

转换到二维： 朴素枚举 $n^2 m^2$ 显然不行
考虑枚举一个矩形的上下边，然后用列前缀和转化成一个新的一维问题， 复杂度 $n^2 m$

但是注意到 $nm < 3e5$
根号分治
当 $n > m$ 时可以进行行列转置
复杂度变成了$n m \sqrt{n m}$

另外用一个桶数组可以代替map, 减少一个log的复杂度， 可能会有负数，所以考虑加上 $nm$ 的偏移量

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define dbg(x) cout << #x << " " << x << endl 
#define int ll 

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> M(n+5,vector<int> (m+5)), tmp(n+5,vector<int> (m+5));
    // 枚举矩阵的上下两端，前缀预处理变成一维，复杂度N*2*M
    // m > n 根号分治 交换矩阵
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char c;
            cin >> c;
            M[i][j] = (c == '#' ? 1 : -1);
        }
    }

    if (n > m) {
        vector<vector<int>> tmp(m+5,vector<int> (n+5));
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                tmp[m-j+1][i] = M[i][j];  
            }
        }
        swap(n, m);
        M = tmp;
    }

    vector<vector<int>> pre(m+1,vector<int>(n+1)); 

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            pre[i][j] = M[j][i] + pre[i][j-1];
        }
    }
    int ans = 0;

    vector<int> mp(2*n*m+10); // 桶计数，增加偏移量n*m;
    mp[n * m] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            vector<int> a(m+1);
            for (int k = 1; k <= m; k++) {
                a[k] = pre[k][j] - pre[k][i-1];
                a[k] += a[k-1];
                ans += mp[a[k] + n*m];
                mp[a[k] + n*m]++;
            }
            for (int k = 1; k <= m; k++) {
                mp[a[k] + n*m]--;
            }
        }
    }
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int tt = 1;
    cin >> tt;
    while (tt--) solve();
    return 0;
}