小A的柱状图

题意： 给定个矩形的宽和高，求可以得到的矩形的最大面积。
题解1：
本题一眼看上去就是笛卡尔树的题，可惜笛卡尔树当时学到半路放弃了。回想过来笛卡尔树是由单调栈延伸过来的，所以考虑能不能用单调栈瞎搞。
本题的难点在于如何处理一定宽度和高构成的矩形面积，即可能更长的宽度和较短的高度也会构成更大的面积。
考虑单调栈，由于短板决定高度，所以要构造一个单调递增的栈。

• 当时，直接入栈，最后的栈一定是单调递增的，所以对于栈内每个元素，出栈时其必然比之前的元素高度低，所以可以直接叠加他们的宽度计算。
• 当时，短板决定高度，所以要将当前栈的所有元素高度全部切成不高于才能继续发挥作用。切成的高度相当于给增加宽度，所以对于栈内每个元素，出栈时其必然比之前的元素高度低，所以可以直接叠加他们的宽度计算。
• 最后得到的单调递增栈，依然是：出栈时其必然比之前的元素高度低，所以可以直接叠加他们的宽度计算。这里的技巧是增加一个，高度为，使得栈中的元素被迫直接出栈。
  注意要开long long

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1e6 + 10;
struct Node{
    int h, w;
}p[N];
int n;

Node stk[N];
int top;

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

    ll res = 0;
    for(int i = 1; i <= n + 1; ++i) {
        if(top == 0 || stk[top].h < p[i].h) stk[++top] = p[i];
        else {
            if(stk[top].h == p[i].h) stk[top].w += p[i].w;
            else {
                //切成p[i].h高度 
                int len = 0;
                while(top > 0 && stk[top].h > p[i].h) {
                    len += stk[top].w;
                    res = max(res, 1ll * stk[top].h * len) ;
                    --top;
                } 
                while(top > 0 && stk[top].h == p[i].h) {
                    len += stk[top].w;
                    --top;
                }
                p[i].w += len;
                stk[++top] = p[i];
            }
        }
    }

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

    return 0;
}

题解2：
学习了https://blog.nowcoder.net/n/e1d2ba3f75284f678e546374ce5e569b
后，理解了点笛卡尔树。
本题直观做法就是以每个矩形高度为标准，向左向右得到最长的宽度。
那么建立小根堆笛卡尔树后，根的左右子树中每个元素的高度都大于等于根的元素高度，从根结点开始，即可求得左右子树加上自身可以得到的最大宽度。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 1e6 + 10;
int ls[N], rs[N];
int stk[N], top;
ll res = 0;

struct Node{
    int h, w;
}p[N];
int n;

void build() {
    top = 0;
    for(int i = 1; i <= n; ++i) {
        int temp = top;
        while(p[stk[temp]].h > p[i].h) --temp;
        if(temp) rs[stk[temp]] = i;
        if(temp < top) ls[i] = stk[temp + 1];
        stk[++temp] = i;
        top = temp;
    }
}

int dfs(int u) {
    if(!u) return 0;
    int sz = p[u].w;
    sz += dfs(ls[u]);
    sz += dfs(rs[u]);
    res = max(res, 1ll * sz * p[u].h);
    return sz;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) scanf("%d", &p[i].w);
    for(int i = 1; i <= n; ++i) scanf("%d", &p[i].h);

    build();

    dfs(stk[1]);

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

    return 0;
}