题目描述

https://loj.ac/problem/3177

题解

假设某个合法的矩形只有一行,是$a_{1,l}\sim a_{1,r}$,那么显然有这样一个结论成立:$a_{1,l-1}$是$a_{1,r+1}$左侧第一个大于它的 或者$a_{1,r+1}$是$a_{1,l-1}$右侧第一个大于它的

那么对于一个合法矩形,每一行都应该满足这个条件

每一列应该也要满足类似的条件

所以对于一行(或列),可以通过单调栈来求出所有这样的$[l,r]$

对于每一行都用这样的方法求出这样的$[l,r]$,用一个vector:$ok[l][r]$来存储所有$a_{i,l}~a_{i,r}$为合法段的$i$

枚举矩形右边界$r$,并每次更新$lok[u][d]$表示只考虑列的限制,当矩形的上下边界为u,d,右边界为r时,左边界最左是哪里

然后枚举矩形左边界$l$,枚举$ok[l][r]$中的每一个连续段$[u,d]$,那么矩形的上下边界在$[u,d]$中时一定是满足行的限制的,只需找出有多少个左右边界为$l,r$,上下边界在$[u,d]$内的矩形满足条件即可

代码中做了注释

代码

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
#include <bits/stdc++.h>
#define N 2520
using namespace std;

template <typename T>
inline void read(T &num) {
T x = 0, f = 1; char ch = getchar();
for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
num = x * f;
}

int n, m, a[N][N], stk[N], cnt, top, ans;
vector<int> ok[N][N]; //ok[l][r]: a[l][i]~a[r][i]为合法段的i的集合
pair<int, int> tmp[N]; //临时存答案
int lok[N][N], rok[N][N];

void solve(int *num, int len) { //找出所有合法段
cnt = top = 0;
for (int i = 1; i <= len; i++) {
while (top && num[i] > num[stk[top]]) {
if (i > stk[top] + 1) tmp[++cnt] = make_pair(stk[top]+1, i-1);
//num[l] < num[r]
top--;
}
if (top) {
if (i > stk[top] + 1) tmp[++cnt] = make_pair(stk[top]+1, i-1);
//num[l]>num[r]
if (num[i] == num[stk[top]]) top--;
//特殊处理相等情况
}
stk[++top] = i;
}
}

void calc(int l, int r, int u, int d) {
//左右边界为l,r;上下边界在[u,d]内
int len = 0;
for (int i = u - 1; i <= d + 1; i++) {
a[0][++len] = a[i][r];
}
solve(a[0], len); //找出列的合法段
for (int i = 1; i <= cnt; i++) {
int tl = tmp[i].first + u - 2, tr = tmp[i].second + u - 2;
if (lok[tl][tr] <= l) ans++;
}
}

int main() {
read(n); read(m);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
read(a[i][j]);
}
}
for (int i = 2; i < n; i++) { //预处理ok集合
solve(a[i], m);
for (int j = 1; j <= cnt; j++) ok[tmp[j].first][tmp[j].second].push_back(i);
}
for (int r = 2; r < m; r++) { //枚举矩形右边界
for (int i = 1; i <= n; i++) a[0][i] = a[i][r];
solve(a[0], n);
for (int i = 1; i <= cnt; i++) {
if (rok[tmp[i].first][tmp[i].second] + 1 < r)
lok[tmp[i].first][tmp[i].second] = r;
rok[tmp[i].first][tmp[i].second] = r;
//lok[u][d]表示只考虑列的限制,当矩形的上下边界为u,d,右边界为r时,左边界最左是哪里
}
for (int l = 2; l <= r; l++) { //枚举矩形左边界
if (!ok[l][r].size()) continue;
int lst = ok[l][r][0];
for (int i = 1; i < ok[l][r].size(); i++) {
if (ok[l][r][i] > ok[l][r][i-1] + 1) {
//找出ok[l][r]中的一个连续段
calc(l, r, lst, ok[l][r][i-1]);
lst = ok[l][r][i];
}
}
calc(l, r, lst, ok[l][r][ok[l][r].size()-1]);
}
}
printf("%d\n", ans);
return 0;
}

评论