spoj 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

题意：给你一个n*m的矩阵，求以一个最小值为m的最大矩阵面积s需要大于等于K

思路:二分答案，check怎么写呢。。

　　类似bzoj 3039这题；

　　利用单调栈，求最大子矩阵面积；

　　将check的x,大于等于x的值均改成1，求1的最大面积；

　　枚举每个位置，以该位置能最大的上升的位置为权值；

　　例如：

　　 1 0 1 1 0 1

　　 1 1 0 --> 2 1 0

　　 1 0 1 3 0 1

　　利用单调栈查找以该权值为最大值最多可以往左和往右延伸最大长度；

　　详见代码

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cmath>
#include<string>
#include<queue>
#include<algorithm>
#include<stack>
#include<cstring>
#include<vector>
#include<list>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define pi (4*atan(1.0))
#define eps 1e-14
#define bug(x)  cout<<"bug"<<x<<endl;
const int N=1e3+10,M=1e6+10,inf=2147483647;
const ll INF=1e18+10,mod=1e9+7;
int a[N][N],b[N][N];
int l[N],r[N],s[N];
int dp[N][N];
int n,m,k;
int check(int x)
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        b[i][j]=(a[i][j]>=x);
    memset(dp,0,sizeof(dp));
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        if(b[i][j])dp[i][j]=dp[i-1][j]+1;
        else dp[i][j]=0;
        dp[i][0]=dp[i][m+1]=-1;
        int si=0;
        s[++si]=0;
        for(int j=1;j<=n;j++)
        {
            while(dp[i][s[si]]>=dp[i][j])si--;
            l[j]=s[si];
            s[++si]=j;
        }
        si=0;
        s[++si]=m+1;
        for(int j=m;j>=1;j--)
        {
            while(dp[i][s[si]]>=dp[i][j])si--;
            r[j]=s[si];
            s[++si]=j;
        }
        for(int j=1;j<=m;j++)
            ans=max(ans,(r[j]-l[j]-1)*dp[i][j]);
    }
    return ans;
}
int main()
{
    int T,cas=1;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                scanf("%d",&a[i][j]);
        int st=0;
        int en=1e9+10,ans=-1;
        while(st<=en)
        {
            int mid=(st+en)>>1;
            if(check(mid)>=k)
            {
                ans=mid;
                st=mid+1;
            }
            else
                en=mid-1;
        }
        printf("%d %d
",ans,check(ans));
    }
    return 0;
}