牛客小白月赛13-H（单调栈+树状数组）

题目链接：https://ac.nowcoder.com/acm/contest/549/H

题意：给一个柱状图，包括每个矩阵的宽度和高度，求能组成的最大矩阵的面积。

思路：显然最大矩阵的高一定为n个矩阵中的一个矩阵的高，所以不访用单调栈求出每个矩阵左边、右边第一个高度小于该矩阵的下标。然后用树状数组求出该区间的宽度和，遍历一遍即可得到结果。算法复杂度O(nlogn)，顺便吐槽这题数据，一朋友没用单调栈暴力求区间，复杂度为O(n^2)，竟然也过了。。

AC代码：

#include<cstdio>

using namespace std;

typedef long long LL;

const int maxn=;

int n,p;

int h[maxn],stk[maxn],L[maxn],R[maxn];

LL tr[maxn],ans;

int lowbit(int x){

    return x&(-x);

}

void update(int x,int num){

    while(x<=n){

        tr[x]+=num;

        x+=lowbit(x);

    }

}

int query(int x){

    int ans=;

    while(x>){

        ans+=tr[x];

        x-=lowbit(x);

    }

    return ans;

}

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;++i){

        int tmp;

        scanf("%d",&tmp);

        update(i,tmp);

    }

    for(int i=;i<=n;++i)

        scanf("%d",&h[i]);

    h[]=h[n+]=;

    stk[p=]=;

    for(int i=;i<=n;++i){

        while(h[stk[p]]>=h[i]) --p;

        L[i]=stk[p]+;

        stk[++p]=i;

    }

    stk[p=]=n+;

    for(int i=n;i>=;--i){

        while(h[stk[p]]>=h[i]) --p;

        R[i]=stk[p]-;

        stk[++p]=i;

    }

    for(int i=;i<=n;++i){

        int w=query(R[i])-query(L[i]-);

        if(1LL*w*h[i]>ans) ans=1LL*w*h[i];

    }

    printf("%lld\n",ans);

    return ;

}