[原创]SPOJ MINSUN Largest Submatrix [二分+单调栈]

2017-01-08 15:18:59 Tabris_ 阅读数：268

博客爬取于2020-06-14 22:42:25
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54234049

题目链接：http://www.spoj.com/problems/MINSUB/
---------------------------------------------------------------------------------------.
MINSUB - Largest Submatrix
no tags
You are given an matrix M (consisting of nonnegative integers) and an integer K. For any submatrix of M’ of M define min(M’) to be the minimum value of all the entries of M’. Now your task is simple: find the maximum value of min(M’) where M’ is a submatrix of M of area at least K (where the area of a submatrix is equal to the number of rows times the number of columns it has).

Input

The first line contains a single integer T (T ≤ 10) denoting the number of test cases, T test cases follow. Each test case starts with a line containing three integers, R (R ≤ 1000), C (C ≤ 1000) and K (K ≤ R * C) which represent the number of rows, columns of the matrix and the parameter K. Then follow R lines each containing C nonnegative integers, representing the elements of the matrix M. Each element of M is ≤ 10^9

Output

For each test case output two integers: the maximum value of min(M’), where M’ is a submatrix of M of area at least K, and the maximum area of a submatrix which attains the maximum value of min(M’). Output a single space between the two integers.

Example

Input:
2
2 2 2
1 1
1 1
3 3 2
1 2 3
4 5 6
7 8 9

Output:
1 4
8 2
------------------------------------------------------------------------------------------.

题目大意：问你找到一个面积大于K的子矩阵中的最小值，在保证最小值最大的情况下计算面积的最大值

解题思路：
首先最小值最大这种就想到了二分，甚至都想到了每次将 $>=mid$ 的值用一表示,其他用0表示,然后枚举子矩阵的左上角和右下角二维树状数组计算值,这样的话总复杂度就到了 $O(n^4*log_2^3 n)$
然后就不会了
看了wannaflyunion的题解才知道用一个叫做单调栈的东西能在 $O(nm)$ 的复杂度中解决求子矩阵的最大值
想法也同样是每次将 $>=mid$ 的值用一表示,其他用0表示.增加的是在这个过程中处理了每个点向左的1的个数,然后通过维护每一列的时候向上有几个不小于这个值的向下有几个不小于这个值的. 这个过程通过单调栈能做到 $O(n)$ ,然后判断的是 $m$ 列的所以总复杂度最后只到了 $O(nmlog_2(1e9+1))$

因为二分的不同写法注意下1e9这个值就好了,

附本题代码
-----------------------------------------------------.

再次抄袭wannaflyunion的代码..
# include <bits/stdc++.h>

using namespace std;

# define INF        (~(1<<31))
# define INFLL      (~(1ll<<63))
# define pb         push_back
# define mp         make_pair
# define abs(a)     ((a)>0?(a):-(a))
# define lalal      puts("*******");
# define s1(x)      scanf("%d",&x)
# define Rep(a,b,c) for(int a=(b);a<=(c);a++)
# define Per(a,b,c) for(int a=(b);a>=(c);a--)

typedef long long int LL ;
typedef unsigned long long int uLL ;

const int MOD = 1e9+7;
const int N = 100000+5;
const double eps = 1e-6;
const double PI = acos(-1.0);
void fre()
{
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
}
/*************************************************/

int n,m,k;
int a[1005][1005],f[1005][1005],U[1005],D[1005];

int check(int x){
    memset(f,0,sizeof(f));
    memset(U,0,sizeof(U));
    memset(D,0,sizeof(D));

    Rep(i,1,n)Rep(j,1,m)
    if(a[i][j]>=x)f[i][j]=f[i][j-1]+1;
    else f[i][j]=0;

    int now ,area = 0;
    Rep(i,1,m){
        Rep(j,1,n){
            now = j-1;
            while(now&&f[j][i]<=f[now][i]) now = U[now];
            U[j] = now ;
        }
        Per(j,n,1){
            now = j+1;
            while(now!=n+1&&f[j][i]<=f[now][i]) now = D[now];
            D[j] = now;
        }
        Rep(j,1,n) area = max(area,(D[j]-U[j]-1)*f[j][i]);
    }
    return area;
}

int main()
{
    int _;
    while(~s1(_)){
        while(_--){
            s1(n),s1(m),s1(k);
            Rep(i,1,n)Rep(j,1,m) s1(a[i][j]);

            int l,r = -1,mid,ans;
            l = 0,r = 1e9+1,ans =0;
            while(l<=r){
                mid = (l+r)>>1;
                if(check(mid)>=k)    ans = mid, l=mid+1;
                else    r=mid-1;
            }
            printf("%d %d\n",ans,check(ans));
        }
    }
    return 0;
}