自动搬运

查看原文

来自洛谷，原作者为

	fast_photon 彼女の目の中の涙が私の心をやけどした

搬运于2025-08-24 23:07:55，当前版本为作者最后更新于2025-01-09 13:43:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

0. 前言

绝世 NL 题。
标算是单 $\log$（看了 github 仓库），但是我双 $\log$ 和线性过的。

1. 分析

1.1 双 $\log$ 乱冲

考虑到，如果一个正方形合法，那么完全被它包含的正方形都没有贡献。因此只需要考虑极大正方形。（极大正方形：固定任意一个顶点，将另一个顶点背离它斜向走一格，得到的正方形总是不合法）。由此可以想到，对于每个格子，以它为左上角的极大正方形存在且唯一。

固定左上角后发现大于极大正方形的一定不合法，小于等于的一定合法，可以通过二维前缀和算区域内障碍个数判断区域是否合法。现在我们得到了 $nm$ 个极大正方形，只需要做一个二维平面上的区域 check max 全局求结果问题。

一刻也没有为扫描线的难处理感到烦恼，立刻赶到现场的是二维数据结构！直接使用类似二维线段树的东西：$f_{i,j,u,v}$ 表示从 $(i,j)$ 这个格子开始，向左上覆盖一个宽度 $2^u$、高度 $2^v$ 的矩形，要求 $2^u\mid i\land 2^v\mid j$。$(i,u),(j,v)$ 分别有 $2n,2m$ 个有效取值，总有效状态数是 $\Theta(nm)$ 的。由于两维相互独立，对于一个边长为 $l$ 的正方形按照线段树分析发现每一维都拆成 $2\log l$ 个区间，总区域个数 $\Theta(\log^2 l)$。
总复杂度 $\Omicron(nm\log n\log m)$。下放标记是状态数复杂度的，当然是 $\Theta(nm)$。

#include<iostream>
#include<cstdio>

using namespace std;

int n, m, a[2005][2005], s[2005][2005];

short f[2005][2005][11][11];

string A[2005];

int lg2(int x) {
    int k = 1, cnt = 0;
    while(k < x) k <<= 1, cnt++;
    return cnt;
}

inline int lowbit(int x) { return x & -x; }
inline int highbit(int x) { return 1 << (31 - __builtin_clz(x)); }

void flush(int i, int j, int di, int dj, int l) {
	int k1, k2;
	for(int x = i + di - 1; x >= i; x -= (1 << k1)) {
		k1 = __builtin_ctz(min(lowbit(x), highbit(x - i + 1)));
		for(int y = j + dj - 1; y >= j; y -= (1 << k2)) {
			k2 = __builtin_ctz(min(lowbit(y), highbit(y - j + 1)));
			f[x][y][k1][k2] = max(f[x][y][k1][k2], (short)l);
		}
	}
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> A[i];
        for(int j = 1; j <= m; j++) {
            a[i][j] = (A[i][j - 1] == '#');
            s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j];
        }
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            int l = 0, r = min(n - i + 1, m - j + 1);
            while(l < r) {
                int mid = (l + r + 1) >> 1;
                if(s[i + mid - 1][j + mid - 1] - s[i - 1][j + mid - 1] - s[i + mid - 1][j - 1] + s[i - 1][j - 1]) r = mid - 1;
                else l = mid;
            }
            if(i >= 2 && j >= 2 && j >= 2 && !(s[i + l - 1][j - 1] - s[i - 1][j - 1] - s[i + l - 1][j - 2] + s[i - 1][j - 2] + s[i - 1][j + l - 1] - s[i - 1][j - 1] - s[i - 2][j + l - 1] + s[i - 2][j - 1] + a[i - 1][j - 1])) continue;
            flush(i, j, l, l, l);
        }
    }
    for(int u = 10; u > 0; u--) {
        for(int v = 10; v >= 0; v--) {
            for(int i = (1 << u); i <= n; i += (1 << u)) {
                for(int j = (1 << v); j <= m; j += (1 << v)) {
                    f[i][j][u - 1][v] = max(f[i][j][u - 1][v], f[i][j][u][v]);
                    f[i - (1 << (u - 1))][j][u - 1][v] = max(f[i - (1 << (u - 1))][j][u - 1][v], f[i][j][u][v]);
                }
            }
        }
    }
    for(int u = 10; u >= 0; u--) {
        for(int v = 10; v > 0; v--) {
            for(int i = (1 << u); i <= n; i += (1 << u)) {
                for(int j = (1 << v); j <= m; j += (1 << v)) {
                    f[i][j][u][v - 1] = max(f[i][j][u][v - 1], f[i][j][u][v]);
                    f[i][j - (1 << (v - 1))][u][v - 1] = max(f[i][j - (1 << (v - 1))][u][v - 1], f[i][j][u][v]);
                }
            }
        }
    }
    int q; cin >> q; while(q--) {
        int x, y; cin >> x >> y;
        cout << (int)f[x][y][0][0] * f[x][y][0][0] << '\n';
    }
}

1.2 线性乱爆

首先二分矩形边长是无比丑陋的，考虑如下维护方式：

• 计算每个位置向右、向下的第一个障碍。
• 自下而上、自右而左搜整个区域。
• 如果一个左上角不能达到其右下一格的答案 $+1$，则它必然被自己右侧或下侧某个障碍卡住，距离取 $\min$。
• 否则就是右下答案 $+1$。

现在只有在数据结构上更新矩形的部分是 $\log^2$ 的，其余部分都是 $\Omicron(nm)$。我们不妨假设更新矩形是不可优化的，考虑优化被更新矩形的个数。
注意到 $\log^2 l=\omicron(l)$，那么如果找到一个矩形可以直接干掉 $\Theta(l)$ 个矩形，不就做完了吗？

发现每个矩形一定被右侧、下侧或右下的某个障碍卡住。右侧和下侧是对称的。

• 如果右侧下侧都没有，那么只有正方形右下方那格有障碍。考虑直接把主对角线的格子全 ban 掉就可以：它们一定被当前正方形包含。
• 否则不妨设下侧有，只考虑贴着下边缘的、最靠左的障碍，那么可以先沿着主对角线移动一些距离到该障碍的上空，并 ban 掉沿路的格子。接下从原本的格子出发，向正下移动到障碍的左上方，并 ban 掉沿路的格子。这些格子为左上角的正方形也一定被相同障碍卡住。

这样的代价是容易分析的：同一个方向（正右、右下、正下）不会 ban 掉一个格子两次（否则这两次 ban 的发出者一定会先有一个 ban 掉另一个）。因此，每个格子最多被 ban 掉 $3$ 次，若干个边长为 $l_1,l_2,\cdots,l_k$ 的矩形会 ban 掉至少 $\dfrac 1 3 \sum l$ 个格子。显然一共只有 $nm$ 个格子，所以有 $\sum l\le 3nm$，则有 $\sum \log^2 l=\Omicron(nm)$。

这样总复杂度就是 $\Theta(nm)$ 了。如下是优化后的核心代码：

for(int i = 1; i <= n; i++) nxr[i][m + 1] = m + 1, nxd[i][m + 1] = i;
for(int j = 1; j <= m + 1; j++) nxr[n + 1][j] = j, nxd[n + 1][j] = n + 1;
for(int i = n; i >= 1; i--) {
	for(int j = m; j >= 1; j--) {
		if(a[i][j]) len[i][j] = 0, nxr[i][j] = j, nxd[i][j] = i;
		else {
			nxr[i][j] = nxr[i][j + 1], nxd[i][j] = nxd[i + 1][j];
			if(!sum(i, j, i + len[i + 1][j + 1], j + len[i + 1][j + 1])) {
				len[i][j] = len[i + 1][j + 1] + 1;
			}
			else len[i][j] = min(nxr[i][j] - j, nxd[i][j] - i);
		}
	}
}
for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= m; j++) {
		int l = len[i][j];
		if(!l || mk[i][j]) continue;
        flush(i, j, l, l, l);
        if(nxr[i + l][j] < j + l) {
        	int k = nxr[i + l][j] - j;
        	for(int v = 0; v <= k; v++) mk[i + v][j + v] = 1;
        	for(int v = 0; v < l - k; v++) mk[i + v][j] = 1;
		}
		else if(nxd[i][j + l] < i + l) {
        	int k = nxd[i][j + l] - i;
			for(int v = 0; v <= k; v++) mk[i + v][j + v] = 1;
			for(int v = 0; v < l - k; v++) mk[i][j + v] = 1;
		}
		else {
			for(int v = 0; v < l; v++) mk[i + v][j + v] = 1;
		}
    }
}

同学给了个单调队列优化成线性的做法，但是没人写代码就先不放了，有空再放上来。