TIOJ 1063 Area ( Deque Monotonicity )

1063 - 最大矩形(Area) | TIOJ INFOR Online Judge
跟這題很像的，不過這次是要求矩形面積。
UVA 12265 Selling Land ( Stack Monotonicity ) - 0w1
很容易注意到，如果先發生的( 左邊開始的 )矩形比後發生的矩形高，那只要先發生的矩形好好的，後面發生的矩形就永遠不會有比左邊更大的矩形面積。但是，左邊的矩形如果比較矮，那麼一開始可能還是面積比較大的，但遲早會被後面比較高的矩形碾壓。所以大致上我們會維護一個高度單調遞增佇列，同時也是面積單調遞檢佇列。最後要注意到的是可能的變化，當一個後面來的矩形比較矮，那麼佇列裡比它矮的矩形都必須因為它跟著變矮。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200 + 2;
const int MAXM = 200 + 2;
typedef pair<int, int> pii;

int n, m;
int G[ MAXN ][ MAXM ];

int h[ MAXM ];

void solve(){
    int ans = 0;
    for(int i = 0; i < n; ++i){
        deque< pii > dq;
        for(int j = 0; j < m; ++j){
            if( G[ i ][ j ] == 0 ){
                dq.clear();
                h[ j ] = 0;
                continue;
            }
            ++h[ j ];
            pii cur = pii( h[ j ], j );
            while( !dq.empty() && dq.back().first >= cur.first ){
                cur.second = dq.back().second;
                dq.pop_back();
            }
            dq.push_back( cur );
            while( !dq.empty() && 
                   dq.front().first * ( j - dq.front().second + 1 ) <
                   dq.back().first * ( j - dq.back().second + 1 ) )
                dq.pop_front();
            ans = max<int>( ans, dq.front().first * ( j - dq.front().second + 1 ) );
        }
    }
    printf("%d\n", ans);
}

int main(){
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            scanf("%d", &G[ i ][ j ]);
    solve();
    return 0;
}