C102 单调栈 P1901 发射站

// 单调栈 O(n)
#include<bits/stdc++.h>
using namespace std;

const int N = 1000005;
int n, h[N], v[N];
int sum[N]; // sum[i]:每个站接收的能量和
int q[N];   // 栈

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> h[i] >> v[i];

    int top = 0;
    for (int i = 1; i <= n; i++)
    {
        while (top && h[q[top]] < h[i])
            sum[i] += v[q[top--]]; // 栈顶的能量给i
        sum[q[top]] += v[i];       // i的能量给栈顶
        q[++top] = i;              // i入栈
    }

    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, sum[i]);
    cout << ans;
    return 0;
}