Monotonic Stack Fundamentals

Monotonic stacks enable linear preprocessing to find:

• Prefix/suffix maximum/minimum positions in sequences
• Next greater/smaller element positions for each index

Problem B3666: Suffix Maximum Positions

Given a dynamically growing array, after each insertion, find all suffix maximum indices and output their XOR sum.

Solution: Maintain a strictly decreasing stack. The XOR sum can be efficiently computed by tracking removed elements.

int main() {
    int n; cin >> n;
    vector<u64> a(n+1);
    stack<u64> stk;
    u64 remove = 0;
    
    auto calc_xor = [](int x) {
        switch(x%4) {
            case 0: return x;
            case 1: return 1;
            case 2: return x+1;
            default: return 0;
        }
    };
    
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        while(!stk.empty() && a[i] >= a[stk.top()]) {
            remove ^= stk.top();
            stk.pop();
        }
        stk.push(i);
        cout << (remove ^ calc_xor(i)) << '\n';
    }
}

Problem P2866: Bad Hair Day

Compute the total number of cows each cow can see to its right.

Solution: For each element, find the next greater or equal element using a monotonic stack.

int main() {
    int n; cin >> n;
    vector<int> a(n+1), next(n+1, n+1);
    stack<int> stk;
    
    for(int i=1; i<=n; i++) {
        cin >> a[i];
        while(!stk.empty() && a[i] >= a[stk.top()]) {
            next[stk.top()] = i;
            stk.pop();
        }
        stk.push(i);
    }
    
    ll ans = 0;
    for(int i=1; i<=n; i++)
        ans += next[i] - i - 1;
    
    cout << ans << '\n';
}

Maximum Subrectangle Techniques

Problem P1578: Maximum Empty Rectangle

Find the largest rectangle not coveirng any given points in an L×W grid.

Solution: Use the plane sweep algorithm with O(n²) complexity:

int main() {
    int L, W, n; cin >> L >> W >> n;
    vector<array<int,2>> points(n+5);
    
    // Add boundary points
    points[n+1] = {0,0};
    points[n+2] = {L,W};
    points[n+3] = {0,W};
    points[n+4] = {L,0};
    n += 4;
    
    // Sort by x-coordinate
    sort(points.begin()+1, points.end());
    ll max_area = 0;
    
    // Horizontal sweep
    for(int i=1; i<=n; i++) {
        int low=0, high=W;
        for(int j=i+1; j<=n; j++) {
            max_area = max(max_area, 1LL*(high-low)*(points[j][0]-points[i][0]));
            if(points[j][1] < points[i][1]) low = max(low, points[j][1]);
            else high = min(high, points[j][1]);
        }
    }
    
    // Sort by y-coordinate
    sort(points.begin()+1, points.end(), [](auto a, auto b) {
        return a[1] < b[1] || (a[1] == b[1] && a[0] < b[0]);
    });
    
    // Vertical sweep
    for(int i=1; i<=n; i++) {
        int left=0, right=L;
        for(int j=i+1; j<=n; j++) {
            max_area = max(max_area, 1LL*(right-left)*(points[j][1]-points[i][1]));
            if(points[j][0] < points[i][0]) left = max(left, points[j][0]);
            else right = min(right, points[j][0]);
        }
    }
    
    cout << max_area << '\n';
}

Suspension Line Method

An O(nm) approach for maximum subrectangle problems:

1. For each point (i,j), compute:

   • h[i][j]: Maximum height of the suspension line
   • left[i][j], right[i][j]: Left and right boundaries

2. The area is then (right[i][j]-left[i][j])*h[i][j]

// Implementation for Problem P4147
int main() {
    int n, m; cin >> n >> m;
    vector<vector<int>> grid(n+1, vector<int>(m+2));
    vector<vector<int>> h(n+1, vector<int>(m+2));
    vector<vector<int>> left(n+1, vector<int>(m+2));
    vector<vector<int>> right(n+1, vector<int>(m+2, m+1));
    
    // Input and initialization
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            h[i][j] = (grid[i][j] == 1) ? h[i-1][j]+1 : 0;
    
    // Compute left boundaries
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            left[i][j] = (grid[i][j] == 1) ? max(left[i-1][j], /* left obstacle */) : 0;
    
    // Compute right boundaries
    for(int i=1; i<=n; i++)
        for(int j=m; j>=1; j--)
            right[i][j] = (grid[i][j] == 1) ? min(right[i-1][j], /* right obstacle */) : m+1;
    
    // Calculate maximum area
    int max_area = 0;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
            max_area = max(max_area, (right[i][j]-left[i][j]-1)*h[i][j]);
    
    cout << max_area*3 << '\n';
}