维护左右边第一个小的值（滑动窗口）

前言：这个题目和我之前写的一个题目差不多，我们可以维护左右边第一个小的，然后我们就可以快速枚举

题目地址

#include <bits/stdc++.h>
using namespace std;
#define ll long longconst int N = (int)1e6 + 10;
int a[N], h[N];
int qian[N];
int n;
int lef[N], rig[N]; // 记录左边和右边第一个小于这个数的坐标void fun() {deque<int> q;for (int i = 1; i <= n; i++) {int u = h[i];while (q.size() && h[q.back()] > u) {int v = q.back();q.pop_back();rig[v] = i;}q.push_back(i);}while (q.size()) {int u = q.back(); q.pop_back();rig[u] = n + 1;}
}void fun1() {deque<int> q;for (int i = n; i; i--) {int u = h[i];while (q.size() && h[q.back()] > u) {int v = q.back();q.back();lef[v] = i;}q.push_back(i);}while (q.size()) {int u = q.back(); q.pop_back();lef[u] = 0;}
}signed main() {cin >> n;for (int i = 1; i <= n; i++) {scanf("%d", &a[i]);qian[i] = qian[i - 1] + a[i];}for (int i = 1; i <= n; i++) {scanf("%d", &h[i]);}fun(); fun1();int ans = 0;for (int i = 1; i <= n; i++) {int hi = h[i];int len = qian[rig[i] - 1] - qian[lef[i]];ans = max(ans, hi * len);}cout << ans;return 0;
}