小A的柱状图（单调队列）

题意：
柱状图中已知每个矩形的宽和高，问矩形最大面积是多少？

思路：
单调栈的模板题，不过也能用单调队列来解决。
对于每个位置，我们可以用单调队列（deque）维护一个单调递增的序列，当遇到递减情况时，统计前面前面形成矩形方案的最大值，同时不断维护队列单调性。（矩形底边宽可以用前缀和预处理求出）
最后记得开 longlong ，应该没什么坑了

代码：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cstring>
#include<deque>
#define mem(a, x) memset(a, x, sizeof(a))
void fre() { freopen("A.txt", "r", stdin); freopen("Ans.txt","w",stdout); }
typedef long long ll;
using namespace std;
int n,i,j;
ll a[1000005],h[1000005],f[1000005];
ll ans = 0;
int main()
{
    deque<int>q;
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>a[i];
        f[i] = f[i-1] + a[i];
    }
    for(i=1;i<=n;i++){
        cin>>h[i];
    }   
    q.push_back(0);   
    for(i=1;i<=n;i++){
        if(q.empty() || h[i] >= h[q.back()]){
            q.push_back(i);
        }
        else{
            while(!q.empty() && h[q.back()] > h[i]){
                ll k = q.back();
                q.pop_back();
                ans = max((f[i-1]-f[q.back()])*h[k],ans);
            }
            q.push_back(i);
        }
    }
    cout<<ans<<endl;
}