[USACO06NOV] Bad Hair Day S
题目描述
农夫约翰有 N N N 头奶牛正在过乱头发节。
每一头牛都站在同一排面朝右，它们被从左到右依次编号为 1 , 2 , ⋯ , N 1, 2, \cdots, N 1,2,⋯,N。编号为 i i i 的牛身高为 h i h_i hi。第 N N N 头牛在最前面，而第 1 1 1 头牛在最后面。
对于第 i i i 头牛前面的第 j j j 头牛，如果 h i > h i + 1 , h i > h i + 2 , ⋯ , h i > h j h_i>h_{i+1}, h_i>h_{i+2}, \cdots, h_i>h_j hi>hi+1,hi>hi+2,⋯,hi>hj，那么认为第 i i i 头牛可以看到第 i + 1 i+1 i+1 到第 j j j 头牛。
定义 C i C_i Ci 为第 i i i 头牛所能看到的牛的数量。请帮助农夫约翰求出 C 1 + C 2 + ⋯ + C N C _ 1 + C _ 2 + \cdots + C _ N C1+C2+⋯+CN。
输入格式
输入共 N + 1 N + 1 N+1 行。
第一行为一个整数
N
N
N，代表牛的个数。
接下来
N
N
N 行，每行一个整数
a
i
a _ i
ai，分别代表第
1
,
2
,
⋯
,
N
1, 2, \cdots, N
1,2,⋯,N 头牛的身高。
输出格式
输出共一行一个整数，代表 C 1 + C 2 + ⋯ + C N C _ 1 + C _ 2 + \cdots + C _ N C1+C2+⋯+CN。
样例 #1
样例输入 #1
6
10
3
7
4
12
2
样例输出 #1
5
提示
数据规模与约定
对于 100 % 100\% 100% 的数据，保证 1 ≤ N ≤ 8 × 1 0 4 1 \leq N \leq 8 \times 10 ^ 4 1≤N≤8×104， 1 ≤ h i ≤ 1 0 9 1 \leq h _ i \leq 10 ^ 9 1≤hi≤109。
代码
#include <iostream>
using namespace std;
const int N = 100010;
int st[N];
int tt = 0;
long long ans;
int main()
{
int n; cin >> n;
while (n--)
{
int x; cin >> x;
//如果当前栈不为空 并且 要进栈的比栈顶还要大 => 出栈
while (tt > 0 && x >= st[tt])
tt--;
ans += tt;
st[++tt] = x;
}
cout << ans;
return 0;
}