问题标题: 酷町堂：问个问题

(H2-6)火箭班阶段六考试  T7 **员不是单调栈吗，我写的是单调栈老师说我写的是模拟，有没有人写了正解给一下？

Code：

#include <bits/stdc++.h>
#include <bits/extc++.h>
int d[1000002], x[1000002], n;
long long val[1000002];
std::vector<int> l, r;
/*
n<=10^6 期望时间复杂度应该是 O(n) 的
很容易写出 O(n^2) 的滑动窗口：
for (int i = 1; i <= n; i++) {
    int l = i, r = i;
    while (l > 1 && d[l - 1] <= d[i])l--;
    while (r < n && d[r + 1] <= d[i])r++;
    l--, r++;
    if (l != i && l != 0)val[l] += x[i];
    if (r != i && r != n + 1)val[r] += x[i];
}
可以发现每次寻找 l 和 r 的时候花费了很多时间，开销在于重复寻找相同的不符合题意的点
如果一个**员 a 向右边的一个**员 b 传递了信息，那么在 b 右边的**员 c 肯定不可能把**传到 b 的左边，因为 b 比左边的大，如果 b 没被选中，那么比 b 还小的都不会被选
考虑建两个栈 l,r 表示**员向左，右传递**的备选**员，如果当前栈顶**员比当前**员等级低，直接弹出
如果剩下空栈，说明当前**员是目前最大的，向左不能传递**，否则栈顶**员一定是第一个比当前**员大的，向右同理
l 顺推，r 要逆推
由于每个**员最多入栈两次 l 一次 r 一次，所以复杂度是 O(n)
*/
int main() {
    std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout.tie(nullptr);
    std::cin >> n;
    for (int i = 1; i <= n; i++) std::cin >> d[i] >> x[i];
    for (int i = 1; i <= n; i++) {
        while (!l.empty() && d[l.back()] <= d[i]) l.pop_back();
        if (!l.empty()) val[l.back()] += (long long)x[i];
        l.push_back(i);
    }
    for (int i = n; i >= 1; i--) {
        while (!r.empty() && d[r.back()] <= d[i]) r.pop_back();
        if (!r.empty()) val[r.back()] += (long long)x[i];
        r.push_back(i);
    }
    return std::cout << *std::max_element(val + 1, val + 1 + n), 0;
}
/*
4
2 2
3 5
6 10
4 3

1st
l=0
r=2 val[2]=2

2nd
l=0
r=3 val[3]=5

3rd
l=0
r=5

4th
l=3 val[3]=8
r=5

val={0,2,8,0}

answer=8
*/