更好的阅读体验：https://www.cnblogs.com/To-Carpe-Diem/p/19524914

大意

直方图中的最大矩形

思路

首先这个题目要求的是长直图中最大的矩形，我们考虑用笛卡尔树去完成这个题目。

首先我们以高度为点权建立笛卡尔树，然后我们如果知道一个点有多少个子节点，那么这个点的矩形并的答案为 $h[i] * sz[i]$，最后全部跑一次即可。

当然，朴素的单调栈也未尝不可，但是笛卡尔树更加形象。

代码

#include<iostream>
#include<stack>
#include<algorithm>
#include<cstring>
using namespace std;

#define int long long
const int MAXN = 1e6 + 10;

int n, a[MAXN];
int l[MAXN], r[MAXN];
int sz[MAXN], in[MAXN];

int dfs(int x){
	if(!x) return 0;
	sz[x] = 1;
	sz[x] += dfs(l[x]);
	sz[x] += dfs(r[x]);
	return sz[x];
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	while(cin >> n && n){
		for(int i = 0;i <= n;i ++){
			l[i] = r[i] = sz[i] = in[i] = 0;
		}
		stack<int> st;
		for(int i = 1;i <= n;i ++){
			cin >> a[i];
		}
		for(int i = 1;i <= n;i ++){
			int last = 0;
			while(!st.empty() && a[st.top()] > a[i]){
				last = st.top();
				st.pop();
			}
			if(!st.empty()){
				r[st.top()] = i;
			}
			l[i] = last;
			st.push(i);
		}
		for(int i = 1;i <= n;i ++){
			if(l[i]) in[l[i]] ++;
			if(r[i]) in[r[i]] ++;
		}
		int root = 0;
		for(int i = 1;i <= n;i ++){
			if(!in[i]){
				root = i;
				break;
			}
		}
		dfs(root);
		int ans = 0;
		for(int i = 1;i <= n;i ++){
			ans = max(ans, a[i] * sz[i]);
		}
		cout << ans << '\n';
	}
	return 0;
}