题解：P13933 [蓝桥杯 2022 省 Java B] 最大子矩阵

· · 题解

发现标签是单调队列，我也不会单调队列，所以写 K-Dtree。

正文

一句话题意（迫真）

求所有满足矩形区域内最大值和最小值的差不大于 lim 的矩形区域的面积的最大值。

解析

那么思路就很清晰了。

我们发现 n 很小，所以直接两层循环枚举矩形的高，而 m，也就是宽，结合简单的最优性策略，我们可以用双指针一遍扫过去。

那么枚举矩形就做到了 O(n^2m) 的复杂度。

然后就是如何得到矩形区域的最大最小值。

这个很显然吧，直接 K-Dtree 维护矩形最大最小值就可以做了。 点数最多是 nm 的，这一步的复杂度可以很容易做到 O(\log nm)。

然后就可以拼起来了，总复杂度 O(n^2m \log nm)，思路很简单，但是码略长。

代码

// code by 樓影沫瞬_Hz17
#include <bits/stdc++.h>
using namespace std;

#define getc() getchar_unlocked()
#define putc(a) putchar_unlocked(a)
#define en_ putc('\n')
#define e_ putc(' ')

using pii = pair<int, int>;

template<class T> inline T in() { 
    T n = 0; char p = getc();
    while (p < '-') p = getc();
    bool f = p == '-' ? p = getc() : 0;
    do n = n * 10 + (p ^ 48), p = getc();
    while (isdigit(p));
    return f ? -n : n;
    return n;
}
template<class T> inline T in(T &a) { return a = in<T>(); }

template<class T> inline void out(T n) {
    if(n < 0) putc('-'), n = -n;
    if(n > 9) out(n / 10);
    putc(n % 10 + '0');
}

template<class T1, class T2> T1 max(T1 a, T2 b) { return a > b ? a : a = b;}
template<class T1, class T2> T1 min(T1 a, T2 b) { return a < b ? a : a = b;}

const int N = 1e5 + 10;

struct pot { // 完全就是 K-Dtree 的模板，有什么不会的自行 oi-wiki
    int x[2], val;
} p[N * 2];

struct node {
    int mi[2], mx[2], val[2]; // 需要维护最大最小值
    int l, r;
    pot p;
} t[N * 2];

inline void up(int u) {
    int l = t[u].l, r = t[u].r;
    for(int i : {0, 1}) {
        t[u].mi[i] = t[u].mx[i] = t[u].p.x[i];
        t[u].val[0] = t[u].val[1] = t[u].p.val;
        if(l) {
            t[u].mi[i] = min(t[u].mi[i], t[l].mi[i]);
            t[u].mx[i] = max(t[u].mx[i], t[l].mx[i]);
            t[u].val[0] = min(t[u].val[0], t[l].val[0]);
            t[u].val[1] = max(t[u].val[1], t[l].val[1]);
        }
        if(r) {
            t[u].mi[i] = min(t[u].mi[i], t[r].mi[i]);
            t[u].mx[i] = max(t[u].mx[i], t[r].mx[i]);
            t[u].val[0] = min(t[u].val[0], t[r].val[0]);
            t[u].val[1] = max(t[u].val[1], t[r].val[1]);
        }
    }
}

int cnt;

inline void build(int&u, int l, int r, int wd) { // 建树 (我在写什么注释啊啊啊，完全不知道应该写什么注释)
    if(l > r) return;
    int m = (l + r) >> 1;
    nth_element(p + l, p + m, p + r + 1, [&](pot a, pot b) { return a.x[wd] < b.x[wd]; });
    t[u = ++ cnt].p = p[m];
    build(t[u].l, l, m - 1, wd ^ 1);
    build(t[u].r, m + 1, r, wd ^ 1);
    up(u);
}

inline bool inr(node p, int mi[2], int ma[2]) { // in range
    return p.mi[0] >= mi[0] and p.mx[0] <= ma[0] and p.mi[1] >= mi[1] and p.mx[1] <= ma[1]; 
}

inline bool outr(node p, int mi[2], int mx[2]) { // out of range
    return p.mi[0] > mx[0] || p.mx[0] < mi[0] || p.mi[1] > mx[1] || p.mx[1] < mi[1];
}

inline bool inr(pot p, int mi[2], int ma[2]) { // in range
    return p.x[0] <= ma[0] and p.x[0] >= mi[0] and p.x[1] <= ma[1] and p.x[1] >= mi[1];
}

inline pii query(int u, int mi[2], int ma[2]) { // 询问
    if(!u) return {200000, -200000};
    if(inr(t[u], mi, ma)) return {t[u].val[0], t[u].val[1]};
    if(outr(t[u], mi, ma)) return{200000, -200000};
    pii l = query(t[u].l, mi, ma), r = query(t[u].r, mi, ma);
    if(inr(t[u].p, mi, ma)) return {min({l.first, r.first, t[u].p.val}), max({l.second, r.second, t[u].p.val})}; // 别忘了单点
    return {min(l.first, r.first), max(l.second, r.second)};
}

signed main() {
    #ifndef ONLINE_JUDGE
        freopen("i.ru", "r", stdin);
        freopen("o", "w", stdout);
    #endif
    int n = in(n), m = in(m), cnp = 0, rt = 0;

    for(int i = 1; i <= n; i ++) {
        for(int j = 1; j <= m; j ++) {
            p[++ cnp] = {{i, j}, in<int>()};
        }
    }

    build(rt, 1, cnp, 0);

    int mi[2], ma[2], lim = in(lim), ans = 0;
    pii t;

    for(int i = 1; i <= n; i ++) {
        for(int j = i; j <= n; j ++) {
            for(int l = 1, r = 1; r <= m;) { // 简单的双指针
                while((r - l + 1) * (j - i + 1) <= ans and r <= m + 1) r ++; // 剪枝，不可能比 ans 优就跳过
                if(r > m) break;
                mi[0] = i, ma[0] = j, mi[1] = l, ma[1] = r;
                t = query(rt, mi, ma);
                if(t.second - t.first <= lim) {
                    ans = max(ans, (r - l + 1) * (j - i + 1));
                    r ++;
                }
                else {
                    l ++, r ++; 
                }
            }
        }
    }
    out(ans);
}   
// 星間~ 干渉~ 融解~ 輪迴~ 邂逅~ 再生~ ララバイ~