2019牛客暑期多校训练营（第三场）F Planting Trees
题意: 一个$N \ast N$ 的矩阵，问最大值和最小值大小差距不超过$M$的最大子矩阵多大。
题解: 题目明示你要使用$O(N^3)$的杂度,暴力枚举子矩阵高度$x$，做一个预处理，把$a[i][j]$到$a[i+x][j]$的最大最小值处理出来，压缩成一行，然后做一次求区间最大值和最小值差值不超过$M$的区间最大长度。
不懂单调队列的可以看看 单调栈和单调队列1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
const int maxn = 5e2 + 5;
struct deq {
static const int start = maxn * 2;
int dat[start * 2];
int l = start;
int r = start;
void push_front(int x) {
dat[l--] = x;
}
void pop_front() {
l++;
}
int front() {
return dat[l + 1];
}
void push_back(int x) {
dat[++r] = x;
}
void pop_back() {
r--;
}
int back() {
return dat[r];
}
int size() {
return r - l;
}
void clear() {
r = l = start;
}
bool empty() {
return r == l;
}
};
deq dqmx, dqmi;
template<typename T>
void read(T &w) { //读入
char c;
while (!isdigit(c = getchar()));
w = c & 15;
while (isdigit(c = getchar()))w = w * 10 + (c & 15);
}
int n, k;
int a[maxn][maxn];
int ans = 0;
int mi[maxn][maxn];
int mx[maxn][maxn];
int main() {
int T;
read(T);
while (T--) {
read(n);
read(k);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
read(a[i][j]);
}
}
ans = 0;
for (int x = 1; x <= n; x++) {
for (int i = n; i >= x; i--) {
int pos = 0;
dqmx.clear();
dqmi.clear();
for (int j = 1; j <= n; j++) {
if (x == 1) {
mx[i][j] = a[i][j];
mi[i][j] = a[i][j];
} else {
mx[i][j] = max(mx[i - 1][j], a[i][j]);
mi[i][j] = min(mi[i - 1][j], a[i][j]);
}
int tmi = mi[i][j], tmx = mx[i][j];
if (tmx - tmi > k) {
dqmi.clear();
dqmx.clear();
pos = j;
} else {
while (dqmi.size() && mi[i][dqmi.back()] > tmi) {
dqmi.pop_back();
}
dqmi.push_back(j);
while (dqmx.size() && mx[i][dqmx.back()] < tmx) {
dqmx.pop_back();
}
dqmx.push_back(j);
while (mx[i][dqmx.front()] - mi[i][dqmi.front()] > k) {
if (dqmx.front() < dqmi.front()) {
pos = dqmx.front();
dqmx.pop_front();
} else {
pos = dqmi.front();
dqmi.pop_front();
}
}
ans = max(ans, x * (j - pos));
}
}
}
}
printf("%d\n", ans);
}
return 0;
}