Introduction to stack optimizations

Stacks can be used to maintain for monotonous properties, can optimize for many problems, but only if you can discover the monotony in the problem.
Here are some problems for exercise from the ant book.
3250 -- Bad Hair Day
POJ 3250 Bad Hair Day
N cows stands in a row, all facing to the right. They can see all the cows as far as all the cows are strictly shorter than itself. Answer the sum of how many cows each cow sees.
Maintain the stack non-increasing, so that the top of the stack is the cow that first blocks the new cow's sight. Because the problem requires that cows can only see those that are strictly shorter than themselves, we cannot pop out equal - height cows, as they still are competitive -- on who came first.

#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
typedef long long ll;
const int MAXN = 8e4 + 4;

int n;
int h[MAXN];
int ans[MAXN];

void solve(){
    stack<int> stk;
    for(int i = n - 1; i >= 0; --i){
        while( !stk.empty() && h[ stk.top() ] </*=*/ h[i] )
            stk.pop(); // non-increasing monotonically 
        ans[i] = stk.empty() ? ( n - 1 - i ) : ( stk.top() - i - 1 );
        stk.push( i );
    }
    ll res = 0LL;
    for(int i = 0; i < n; ++i)
        res += ans[i];
    printf("%lld\n", res);
}

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

2559 -- Largest Rectangle in a Histogram
POJ 2559 Largest rectangle in a histogram
Find the rectangle with largest area.
Notice that the largest rectangle must fill to the highest for some h[i], and extend to both left and right ends as much as it can. So if we could maintain where each h[i] can extend itself to for both sides in O(1), we will only have at most N candidates thus having an O(N) algorithm. This can be done by maintaining a stack, storing indexes, so that the height is strictly increasing monotonically. Imagine scanning from left to right, having some increasing h[i], where of course increasing i as well, now we try to insert a new element. If it is already higher than the h[ top of stack ], we will know that it can reach to at most the index of the top of stack + 1. Otherwise we could pop out some elements from the stack until the condition above is satisfied, then it would still be the same. The intuition of this problem is that we should discard elements that are higher than some elements in their right sides because they will no longer be used -- they can never block some new element from passing through, because some element can block better than them, and will block earlier than them. Basically the stack is maintaining the first threshold that stops the new element from passing through, and that index is what we wish to know.

#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 5;

int n;
int h[MAXN], l[MAXN], r[MAXN];
// l[i]: the most left i can move to, with its height unchanged
void solve(){
    stack<int> stk;
    for(int i = 0; i < n; ++i){
        while( !stk.empty() && h[ stk.top() ] >= h[i] )
            stk.pop();
        l[i] = stk.empty() ? 0 : ( stk.top() + 1 );
        stk.push( i );
    }
    while( !stk.empty() ) stk.pop();
    for(int i = n - 1; i >= 0; --i){
        while( !stk.empty() && h[ stk.top() ] >= h[i] )
            stk.pop();
        r[i] = stk.empty() ? ( n - 1 ) : ( stk.top() - 1 );
        stk.push( i );
    }
    ll ans = 0LL;
    for(int i = 0; i < n; ++i)
        ans = max( ans, (ll)h[i] * ( r[i] - l[i] + 1 ) );
    printf("%lld\n", ans);
}

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

2082 -- Terrible Sets
POJ 2082 Terrible Sets
Same problem like the above, but each width is different.
But it's alright, just use prefix sum for w[i], and it's totally the same.

#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
typedef long long ll;
const int MAXN = 5e4 + 4;

int n;
int w[MAXN], h[MAXN];
int _pw[MAXN * 2], *pw = &_pw[MAXN]; // negative index accessible
int l[MAXN], r[MAXN];

void solve(){
    for(int i = 0; i < n; ++i) // prefix sum for w
        pw[i] = pw[i - 1] + w[i];
    stack<int> stk;
    for(int i = 0; i < n; ++i){
        while( !stk.empty() && h[ stk.top() ] >= h[i] )
            stk.pop();
        l[i] = stk.empty() ? 0 : ( stk.top() + 1 );
        stk.push( i );
    }
    while( !stk.empty() ) stk.pop();
    for(int i = n - 1; i >= 0; --i){
        while( !stk.empty() && h[ stk.top() ] >= h[i] )
            stk.pop();
        r[i] = stk.empty() ? ( n - 1 ) : ( stk.top() - 1 );
        stk.push( i );
    }
    int ans = 0;
    for(int i = 0; i < n; ++i){
        int width = pw[ r[i] ] - pw[ l[i] - 1 ];
        ans = max( ans, h[i] * width );
    }
    printf("%d\n", ans);
}

int main(){
    while( scanf("%d", &n) && n != -1 ){
        for(int i = 0; i < n; ++i)
            scanf("%d %d", &w[i], &h[i]);
        solve();
    }
    return 0;
}

3494 -- Largest Submatrix of All 1’s
POJ 3494 Largest Submatrix of All 1’s
Here's another problem similar to the one above. This time there are m floors of the original problem. So we can enumerate each level as the floor of the original problem, by pre-calculating the height when each block is set as the base of the floor. Of course if the base itself is 0, the height will be 0, and the algorithm above can still handle height of 0 because it will treat it as an ultimate threshold, which will pop out everything as you can see.

#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
const int MAXM = 2000 + 2;
const int MAXN = 2000 + 2;

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

int h[MAXM][MAXN];
void pre_h(){
    for(int i = 1; i <= m; ++i)
        for(int j = 1; j <= n; ++j){
            if( G[i][j] == 0 ) h[i][j] = 0;
            else h[i][j] = h[i - 1][j] + 1;
        }
}

int l[MAXN], r[MAXN];
void enumerate_level(int x, int &ans){
    stack<int> stk;
    for(int i = 1; i <= n; ++i){
        while( !stk.empty() && h[x][ stk.top() ] >= h[x][i] )
            stk.pop();
        l[i] = stk.empty() ? 1 : ( stk.top() + 1 );
        stk.push( i );
    }
    while( !stk.empty() ) stk.pop();
    for(int i = n; i >= 1; --i){
        while( !stk.empty() && h[x][ stk.top() ] >= h[x][i] )
            stk.pop();
        r[i] = stk.empty() ? n : ( stk.top() - 1 );
        stk.push( i );
    }
    for(int i = 1; i <= n; ++i)
        ans = max( ans, h[x][i] * ( r[i] - l[i] + 1 ) );
}

void solve(){
    pre_h();
    int ans = 0;
    for(int i = 1; i <= m; ++i)
        enumerate_level( i, ans );
    printf("%d\n", ans);
}

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