题解：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-wikiint 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 rangereturn 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 rangereturn 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 rangereturn 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_JUDGEfreopen("i.ru", "r", stdin);freopen("o", "w", stdout);#endifint 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);
}   
// 星間~ 干渉~ 融解~ 輪迴~ 邂逅~ 再生~ ララバイ~