进行一个标的爆

fast_photon

2025-01-09 13:43:33

Solution

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

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

进 行 一 个 标 的 爆