SPOJ_MINSUB:Largest_Submatrix(二分+单调栈)

【题意】是说给定一个R*C的非负矩阵,试求出一个包含数字数>=K的子矩阵,使得这个子矩阵中最小的数字最大.
【解题思路】

主要是二分答案,即二分那个最小的数字,然后针对每次二分的值mid,可以将原矩阵根据是否满足A[i][j]>=mid,而转成一个R*C的01矩阵a[][],然后问题求变成了给定一个二维01矩阵,求最大的满1矩阵,可以用单调栈的思想来处理这个子问题,设b[i][j]表示从a[i][j]的位置(包含)向上最多有几个连续的1存在
比如 1 1 0
1 0 1
的b[][]={{1,1,0},{2,0,1}}
然后对于每个i单独处理第i行(即子矩阵是以第i行为下边界的情况),设L[i][j]表示从j开始向左满足b[i][k]>=b[i][j]条件所能延伸到的最大的位置,而R[i][j]类似表示相应能够到的最右的位置
比如 j=1 2 3 4 5 6
b[][j]=4 1 3 2 5 6
则lef[][]=1 1 3 3 5 6
rig[][]=1 6 3 6 6 6

然后求lef[][]和rig[][]的过程对于每行可以运用单调栈在O(n)时限内完成。

SB的把单调栈写错了，竟然还过了样例。。

//
//Created by just_sort 2016/1/5
//Copyright (c) 2016 just_sort.All Rights Reserved
//

//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <time.h>
#include <cstdlib>
#include <cstring>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define REP3(i, a, b) for(int i = a; i >= b; i--)
#define CLR(a, b)     memset(a, b, sizeof(a))
#define MP(x, y)      make_pair(x,y)
const int maxn = 2010;
const int maxm = 2e5;
const int maxs = 10;
const int maxp = 1e3 + 10;
const int INF  = 1e9;
const int UNF  = -1e9;
const int mod  = 1e9 + 7;
int gcd(int x, int y) {return y == 0 ? x : gcd(y, x % y);}
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set;
//head
int getmax(int x, int y)
{
    return x > y ? x : y;
}
int a[maxn][maxn], b[maxn][maxn], L[maxn][maxn], R[maxn][maxn], st[maxn];
int n, m, k, top;

int check(int x)
{
    int ans = 0;
    REP2(j, 1, m) b[1][j] = (a[1][j] >= x);
    REP2(i, 2, n){
        REP2(j, 1, m){
            b[i][j] = (a[i][j] >= x) ? (b[i - 1][j] + 1) : 0;
        }
    }
    REP2(i, 1, n){
        top = st[1] = L[i][1] = 1;
        REP2(j, 2, m){
            while(top > 0 && b[i][st[top]] >= b[i][j]) top--;
            L[i][j] = (top) ? (st[top] + 1) : 1; st[++top] = j;
        }
        top = 1;
        st[1] = R[i][m] = m;
        REP3(j, m - 1, 1){
            while(top > 0 && b[i][st[top]] >= b[i][j]) top--;
            R[i][j] = (top) ? (st[top] - 1) : m; st[++top] = j;
        }
        REP2(j, 1, m) if(b[i][j]) ans = getmax(ans, b[i][j] * (R[i][j] - L[i][j] + 1));
    }
    return ans;
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%d%d%d", &n, &m, &k);
        REP2(i, 1, n){
            REP2(j, 1, m){
                scanf("%d", &a[i][j]);
            }
        }
        int l = 0, r = 1e9;
//        while(l + 1 < r){
//            int mid = (l + r) >> 1;
//            if(check(mid) >= k) l = mid;
//            else r = mid - 1;
//        }
//        if(check(r) >= k) l = r;
//        while(l < r){
//            int mid = (l + r) / 2;
//            if(check(mid) >= k) l = mid + 1;
//            else r = mid - 1;
//        }
//        if(check(r) >= k) l = r;
        while(l < r){
            int mid = (l + r) / 2;
            if(check(mid) >= k) l = mid + 1;
            else r = mid;
        }
        printf("%d %d\n", l - 1, check(l - 1));
    }
    return 0;
}