Histogram (segment tree).cpp

/*     Largest Area in a histogram using segment tree
    1. Build a RMQ segment tree
    2. Query will provide minimum index
    3. Now for a interval (b, e), we have three options -
       (i) take the whole interval
       (ii) take the left interval from the minIndex
       (iii) take the right interval from the minIndex
    4. Take the maximum value using divide and conquer
    Sample solution : LightOJ - 1083 (Histogram)
*/

#include <bits/stdc++.h>

using namespace std;

#define MAX 30008
int arr[MAX], n;

struct data {
    int Min, MinIdx;
} tree[4*MAX];

void init(int node, int b, int e)
{
    if(b == e){
        tree[node].Min = arr[b];
        tree[node].MinIdx = b;
        return;
    }
    int left = 2*node;
    int right = 2*node + 1;
    int mid = (b+e)/2;
    init(left, b, mid);
    init(right, mid+1, e);
    if(tree[left].Min <= tree[right].Min){
        tree[node].Min = tree[left].Min;
        tree[node].MinIdx = tree[left].MinIdx;
    }
    else {
        tree[node].Min = tree[right].Min;
        tree[node].MinIdx = tree[right].MinIdx;
    }
}

int query(int node, int b, int e, int i, int j)
{
    if(i > e || j < b) return -1;
    if(b >= i && e <= j) return tree[node].MinIdx;
    int left = 2*node;
    int right = 2*node + 1;
    int mid = (b+e)/2;
    int p = query(left, b, mid, i, j);
    int q = query(right, mid+1, e, i, j);
    if(p == -1) return q;
    if(q == -1) return p;
    if(arr[p] <= arr[q]) return p;
    else return q;
}

int area(int b, int e)
{
    if(b == e) return arr[b];
    if(b > e) return 0;
    int idx = query(1, 1, n, b, e);
    int res = max(area(b, idx-1), area(idx+1, e));
    int calc = (e-b+1) * arr[idx];
    res = max(res, calc);
    return res;
}

int main()
{
    //freopen("in.txt", "r", stdin);
    int cases;
    scanf("%d", &cases);
    int caseno = 0;
    while(cases--){
        scanf("%d", &n);
        for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
        init(1, 1, n);
        printf("Case %d: %d\n", ++caseno, area(1, n));
    }
}