题解：CF713D Animals and Puzzle

· · 题解

题意

给定一个 n \times m 的 01 矩阵 a，给定 q 个询问，每次给出一个询问矩形的左上角 (x1, y1) 和右下角 (x2, y2)，问这个矩形内的最大全 1 正方形的边长是多少。1 \le n,m \le 1000，1 \le q \le 10^6。

思路

首先考虑暴力，我们希望枚举询问矩形里的每个点，找到这一个点作为右下角的最大正方形（需要特判一下边界）。而每一个点对应的最大正方形边长也可以暴力预处理。时间复杂度 \mathcal{O}(m^2n + nmq)。

::::info[暴力代码] 暴力代码的预处理是把每个点作为右上角的。

#include<bits/stdc++.h>
using namespace std;
template<typename T> inline void read(T &x){
    T s = 0; int st = 1; char c = getchar();
    while(c < '0' || c > '9'){(c == '-') && (st = -1); c = getchar();}
    while(c >= '0' && c <= '9'){s = (s << 3) +(s << 1) + (c ^ 48); c = getchar();}
    x = s * st;
}
template<typename T> inline void write(T x){
    if(x <0) x= -x, putchar('-');
    if(x > 9) write(x / 10);
    putchar(x % 10 + 48);
}
#define LL long long
#define PII pair<int, int>
#define x1 orjsodfjdsofi
#define x2 dsoasgsapofj
#define y1 dlfzgjzdroier
#define y2 erogxlfigures
const int N = 1e3 + 5;
bool a[N][N];
int sum[N][N], sq[N][N];
inline int get1(int x1, int y1, int x2, int y2){
    return sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];
}
int main(){
    int n, m, q;
    read(n), read(m);
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            read(a[i][j]);
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
        }
    }
    for(int i = 1; i <= m; ++i){
        int l = 0, r = 0;
        for(int j = 1; j <= n; ++j){
            if(a[j][i]){
                if(l == 0) l = r = j;
                else r = j;
            }
            else l = r = 0;
            int tmp = r - l + 1;
            if(i + tmp - 1 > m) tmp = m - i + 1;
            if(j - tmp + 1 < 0) tmp = j;
            while(tmp > 0 && get1(j - tmp + 1, i, j, i + tmp - 1) < tmp * tmp){
                --tmp;
            }
            sq[j][i] = tmp;
        }
    } 
    read(q);
    while(q--){
        int x1, x2, y1, y2, ans = 0;
        read(x1), read(y1), read(x2), read(y2);
        for(int i = x1; i <= x2; ++i){
            for(int j = y1; j <= y2; ++j){
                ans = max(ans, min({sq[i][j], i - x1 + 1, y2 - j + 1}));
            }
        }
        write(ans);
        putchar('\n');
    }
    return 0;
}

:::: 时间复杂度式子的每一项都需要优化。

预处理可以通过递推优化成 \mathcal{O}(nm)，设 f_{i, j} 表示以 (i, j) 为右下角的最大正方形边长。这个正方形可以通过 (i - 1, j - 1) 的正方形边长加一拓展而来。但是，我们得保证第 i 行和第 j 列对应边上点都是 1。所以在 a_{i, j} 为 1 时，有转移方程：

f_{i, j} \gets \min(f_{i - 1, j - 1}, f_{i, j - 1}, f_{i - 1, j})+1

当 a_{i, j} 为 0 时，不存在合法正方形，所以有：

f_{i, j} \gets 0

预处理部分优化完成，现在需要优化查询部分。

我们发现，对于一个合法边长 ans，所有边长 x \le ans 的均合法，x \gt ans 的需要再判断。这个过程熟悉吗？二分答案。由于答案具有单调性，我们通过二分答案优化查询时间复杂度至 \mathcal{O}(q\log\min(n,m))，把最值转化成判定性问题。

考虑二分答案的“check”函数。一个合法边长 mid 合法，当且仅当左上角为 (x1 + mid - 1, y1 + mid - 1)，右下角为 (x2, y2) 的矩形内部的“右下角”，所组成的正方形的最大边长 \ge mid 即可。可能有同学对边界条件有疑惑，其实满足在 (x1 + mid - 1, y1 + mid - 1) 右下的“右下角”，如果所对应最大边长 f 值比 mid 大可以通过 (x1, y1) 的边界“截”到 mid 这么长，说明 mid 就是合法的。

问题转化成了求 f 数组上左上角为 (x1 + mid - 1, y1 + mid - 1)，右下角为 (x2, y2) 的矩形的最大值。这里用二维 st 表即可。

一维 st 表是通过两个区间并求得的，二维 st 表就可以通过四个矩形并求。查询同理。

代码

注意 st 表部分容易出错，包括哪些地方有没有 -1 之类的，要仔细。

#include<bits/stdc++.h>
using namespace std;
template<typename T> inline void read(T &x){
    T s = 0; int st = 1; char c = getchar();
    while(c < '0' || c > '9'){(c == '-') && (st = -1); c = getchar();}
    while(c >= '0' && c <= '9'){s = (s << 3) +(s << 1) + (c ^ 48); c = getchar();}
    x = s * st;
}
template<typename T> inline void write(T x){
    if(x <0) x= -x, putchar('-');
    if(x > 9) write(x / 10);
    putchar(x % 10 + 48);
}
#define LL long long
#define PII pair<int, int>
#define x1 orjsodfjdsofi
#define x2 dsoasgsapofj
#define y1 dlfzgjzdroier
#define y2 erogxlfigures
const int N = 1e3 + 1;
int n, m, q;
int f[11][11][N][N], lg[N];
inline void init(){
    for(int k = 1; k <= lg[n]; ++k){
        for(int i = 1; i + (1 << k) - 1 <= n; ++i){
            for(int j = 1; j <= m; ++j){
                f[k][0][i][j] = max(f[k - 1][0][i][j], f[k - 1][0][i + (1 << k - 1)][j]);
            }
        }
    }
    for(int l = 1; l <= lg[m]; ++l){
        for(int i = 1; i <= n; ++i){
            for(int j = 1; j + (1 << l) - 1 <= m; ++j){
                f[0][l][i][j] = max(f[0][l - 1][i][j], f[0][l - 1][i][j + (1 << l - 1)]);
            }
        }
    }
    for(int k = 1; k <= lg[n]; ++k){
        for(int l = 1; l <= lg[m]; ++l){
            for(int i = 1; i + (1 << k) - 1 <= n; ++i){
                for(int j = 1; j + (1 << l) - 1 <= m; ++j){
                    f[k][l][i][j] = max({f[k - 1][l - 1][i][j], 
                        f[k - 1][l - 1][i + (1 << k - 1)][j], 
                        f[k - 1][l - 1][i][j + (1 << l - 1)], 
                        f[k - 1][l - 1][i + (1 << k - 1)][j + (1 << l - 1)]});
                }
            }
        }
    }
}
inline int get(int x1, int y1, int x2, int y2){//左上角, 右下角 
    int lx = lg[x2 - x1 + 1], ly = lg[y2 - y1 + 1];
    return max({f[lx][ly][x1][y1], 
        f[lx][ly][x1][y2 - (1 << ly) + 1], 
        f[lx][ly][x2 - (1 << lx) + 1][y1], 
        f[lx][ly][x2 - (1 <<lx) + 1][y2 - (1 << ly) + 1]});
}
int main(){
    read(n), read(m);
    for(int i = 2; i <= max(n, m); ++i) lg[i] = lg[i >> 1] + 1;
    for(int i = 1, a; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            read(a);
            if(a){
                f[0][0][i][j] = min({f[0][0][i - 1][j], f[0][0][i][j - 1], f[0][0][i - 1][j - 1]}) + 1;
            }
        }
    }
    init();
    read(q);
    while(q--){
        int x1, x2, y1, y2, l, r, mid, ans = 0;
        read(x1), read(y1), read(x2), read(y2);
        l = 1, r = min(y2 - y1 + 1, x2 - x1 + 1);
        while(l <= r){
            mid = l + r >> 1;
            if(get(x1 + mid - 1, y1 + mid - 1, x2, y2) >= mid){
                ans = mid;
                l = mid + 1;
            }
            else{
                r = mid - 1;
            }
        }
        write(ans); putchar('\n');
    }
    return 0;
}
/*
3 4
1 1 0 1
0 1 1 0
0 1 1 0
5
1 1 2 3
2 1 3 2
3 2 3 4
1 1 3 4 
1 2 3 4
*/

讲得有点抽象抱歉。这是今天学校 s 组%你赛 T3，赛时一直在想扫描线树套树之类的东西，最后只把暴力写了拿了 40 分非常遗憾，觉得题目还是有点价值于是克服倦意写了这篇题解。