給一個$n\times m$的01矩陣，問有幾個正方形子矩陣滿足該子矩陣內的數字全都是1，並且輸出最長的邊長。
$n, m\le 5000$
這題有個十分重要的轉換手法，對於每一列我們維護一個長度為m的陣列a，a[i]代表第i行往上有幾個連續的0。
這個手段在TIOJ-1063也有用到。
接下來對每個(i,j)去計算以(i,j)為右下角可用出的正方形最大邊長(可以發現任何它短的邊長的正方形也都能放)。
如果要用長度為$x$的正方形，那必須滿足
$$\min_{k=j-x+1}^{j}(a[k])\ge x$$
由於隨著x變大，min只會越來越小，因此可以二分搜x，做到$\mathcal{O}(nmlogm)$。
如果我們改成考慮可以放出最大正方形的左界$l(l=j-x+1)$，然後就會發現隨著$j$增加，$l$只增不減(因為$j$增加也會使得min越來越小)。
所以可以使用雙指標，並且維護一個遞減的單調隊列來做RMQ(因為查詢的範圍只會越來越右邊)。
這樣就能做到$\mathcal{O}(nm)$。
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
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS = 1e-8;
const int INF = 0x3F3F3F3F;
const ll LINF = 4611686018427387903;
const int MOD = 1e9+7;
signed main() { EmiliaMyWife
int n, m;
cin >> n >> m;
vector<string> arr(n);
for(int i = 0; i < n; i++)
cin >> arr[i];
vector<int> owo(m);
deque<int> line;
ll ans = 0, mx = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(arr[i][j] & 1)
owo[j] = 0;
else
owo[j]++;
}
for(int j = 0, it = 0; j < m; j++) {
while(!line.empty() && owo[line.back()] > owo[j])
line.pop_back();
line.push_back(j);
while(!line.empty() && owo[line.front()] < j - it + 1) {
it++;
if(line.front() < it)
line.pop_front();
}
ans += j - it + 1;
mx = max<ll>(mx, j - it + 1);
}
line.clear();
}
cout << ans << ' ' << mx << '\n';
}
|