算法
(单调栈) $O(n)$
从右往左依次枚举 $i = n, n-1, \cdots, 1$ 的过程中,我们用单调栈维护,有哪些 $j(i \leqslant j \leqslant n)$ 满足 $h_j$ 是 $h_{i+1}, \cdots, h_j$ 中是最大的。只有这样的 $j$, 才有可能成为对当前 $i$ 的合法二元组 $(i, j)$ 中的 $j$。
对于一个 $i$,在所有可能和该 $i$ 组成合法二元组的 $j$ 中,只有最多一个 $j$ 满足 $h_j > h_i$,而其他的 $j$ 都会在处理完该 $i$ 后从单调栈中删除。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::stack;
using ll = long long;
int main() {
int n;
cin >> n;
vector<int> h(n);
rep(i, n) cin >> h[i];
ll ans = 0;
stack<int> stk;
for (int i = n-1; i >= 0; --i) {
while (stk.size() and h[stk.top()] < h[i]) {
ans += stk.top() - i + 1;
stk.pop();
}
if (stk.size()) ans += stk.top() - i + 1;
stk.push(i);
}
cout << ans << '\n';
return 0;
}
厉害