包含全零的子矩阵的数量 [英] Number of submatricies containing all zeros
问题描述
有没有一种方法可以找到许多包含全零的矩形子矩阵，其复杂度小于O(n ^ 3)，其中n是给定矩阵的维数?
Is there a way to find a number of rectangular submatrices containing all zeros with a complexity smaller than O(n^3), where n is the dimension of given matrix?
推荐答案
这是解决方案 O(n²log n).
首先，让我们将主要问题转换为以下内容:
Here is a solution O(n² log n).
First, let's convert the main problem to something like this:
对于给定的直方图，找到包含全零的子矩阵的数量.
For given histogram, find the number of submatrices containing all zeros.
对于每个位置，计算从该位置开始且仅包含零的列的高度.
For each position calculate the height of column that start on that position and contain only zeros.
示例:
10010 01101
00111 12000
00001 -> 23110
01101 30020
01110 40001
可以在O(n²)中轻松找到它.
It can be easily find in O(n²).
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
up[i][j] = arr[i][j] ? 0 : 1 + up[i - 1][j];
现在，我们可以将每一行视为具有给定高度的直方图.
Now we can consider each row as histogram with given heights.
我们的目标是从左向右移动所有高度，并且在每一步上我们将更新数组L.每个高度的此数组将包含最大宽度，以便我们可以从当前位置到左侧并以给定高度创建一个具有此宽度的矩形.
Our goal is to travel all heights from left to right, and on each step we are going to update array L. This array for each height is going to contain maximum widths so that we can make a rectangle of this width from current position, to the left and of given height.
考虑示例:
0
0 0
0 000
00000 -> heights: 6 3 4 4 5 2
000000
000000
L[6]: 1 0 0 0 0 0
L[5]: 1 0 0 0 1 0
L[4]: 1 0 1 2 3 0
L[3]: 1 2 3 4 5 0
L[2]: 1 2 3 4 5 6
L[1]: 1 2 3 4 5 6
steps: 1 2 3 4 5 6
如您所见，如果我们将所有这些数字相加，我们将收到给定直方图的答案.
As you can see if we add all those numbers we will receive an answer for given histogram.
我们可以简单地更新O(n)中的数组L，但是我们也可以通过使用段树(具有惰性传播)在O(log n)中进行更新，该段树可以添加间隔，在间隔中设置值并从中获取和间隔.
We can simply update array L in O(n), however we can also do it in O(log n) by using segment tree (with lazy propagation) that can add in interval, set value in interval and get sum from interval.
在每个步骤中，我们只需在区间[1，height]上加1，并在区间[height + 1，maxHeight]中设置0，然后从区间[1，maxHeight]中求和.
In each step we just add 1 to interval [1, height] and set 0 in interval[height + 1, maxHeight] and get sum from interval [1, maxHeight].
height-直方图中当前列的高度.
height - height of current column in histogram.
maxHeight-直方图中列的最大高度.
maxHeight - maximum height of column in histogram.
那就是您如何获得O(n²* log n)解决方案:)
And thats how you can get O(n² * log n) solution :)
const int MAXN = 1000;
int n;
int arr[MAXN + 5][MAXN + 5]; // stores given matrix
int up[MAXN + 5][MAXN + 5]; // heights of columns of zeros
long long answer;
long long calculate(int *h, int maxh) { // solve it for histogram
clearTree();
long long result = 0;
for(int i = 1; i <= n; i++) {
add(1, h[i]); // add 1 to [1, h[i]]
set(h[i] + 1, maxh); // set 0 in [h[i] + 1, maxh];
result += query(); // get sum from [1, maxh]
}
return result;
}
int main() {
ios_base::sync_with_stdio(0);
cin >> n;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
cin >> arr[i][j]; // read the data
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
up[i][j] = arr[i][j] ? 0 : 1 + up[i - 1][j]; // calculate values of up
for(int i = 1; i <= n; i++)
answer += calculate(up[i], i); // calculate for each row
cout << answer << endl;
}
这是代码的开始，段树:
#include <iostream>
using namespace std;
// interval-interval tree that stores sums
const int p = 11;
int sums[1 << p];
int lazy[1 << p];
int need[1 << p];
const int M = 1 << (p - 1);
void update(int node) {
if(need[node] == 1) { // add
sums[node] += lazy[node];
if(node < M) {
need[node * 2] = need[node * 2] == 2 ? 2 : 1;
need[node * 2 + 1] = need[node * 2 + 1] == 2 ? 2 : 1;
lazy[node * 2] += lazy[node] / 2;
lazy[node * 2 + 1] += lazy[node] / 2;
}
} else if(need[node] == 2) { // set
sums[node] = lazy[node];
if(node < M) {
need[node * 2] = need[node * 2 + 1] = 2;
lazy[node * 2] = lazy[node] / 2;
lazy[node * 2 + 1] = lazy[node] / 2;
}
}
need[node] = 0;
lazy[node] = 0;
}
void insert(int node, int l, int r, int lq, int rq, int value, int id) {
update(node);
if(lq <= l && r <= rq) {
need[node] = id;
lazy[node] = value * (r - l + 1);
update(node);
return;
}
int mid = (l + r) / 2;
if(lq <= mid) insert(node * 2, l, mid, lq, rq, value, id);
if(mid + 1 <= rq) insert(node * 2 + 1, mid + 1, r, lq, rq, value, id);
sums[node] = sums[node * 2] + sums[node * 2 + 1];
}
int query() {
return sums[1]; // we only need to know sum of the whole interval
}
void clearTree() {
for(int i = 1; i < 1 << p; i++)
sums[i] = lazy[i] = need[i] = 0;
}
void add(int left, int right) {
insert(1, 0, M - 1, left, right, 1, 1);
}
void set(int left, int right) {
insert(1, 0, M - 1, left, right, 0, 2);
}
// end of the tree
这篇关于包含全零的子矩阵的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
