[COI2007] Patrik 音乐会的等待
题目描述
\(n\) 个人正在排队进入一个音乐会。人们等得很无聊，于是他们开始转来转去，想在队伍里寻找自己的熟人。
队列中任意两个人 \(a\) 和 \(b\)，如果他们是相邻或他们之间没有人比 \(a\) 或 \(b\) 高，那么他们是可以互相看得见的。
写一个程序计算出有多少对人可以互相看见。
输入格式
输入的第一行包含一个整数 \(n\)，表示队伍中共有 \(n\) 个人。
接下来的 \(n\) 行中，每行包含一个整数，表示人的高度，以毫微米(等于 \(10^{-9}\) 米)为单位，这些高度分别表示队伍中人的身高。
输出格式
输出仅有一行，包含一个数 \(s\)，表示队伍中共有 \(s\) 对人可以互相看见。
样例 #1
样例输入 #1
7
2
4
1
2
2
5
1
样例输出 #1
10
提示
数据规模与约定
对于全部的测试点，保证 \(1\le\) 每个人的高度 \(< 2^{31}\)，\(1 \le n \le 5\times 10^5\)。
暴力枚举：\(O(n^2)\)超时，观察单调性质，发现可以使用单调栈。
单调栈的用处
1）在数列中线性找到第一个比ai大的aj（i<j）
2）找到两元素间所有元素均(不)大/小于这两者”的问题
1）是模板题
2）是这道题
考虑维护单调下降的身高单调栈。如果是空栈，将第一个元素加入。从 \(a_2\) 遍历到 \(a_n\)，对于 \(a_i\) 如果其大于了栈顶，则持续弹出栈，直到 \(a_i\le ddz.top\)。这道题有相同身高问题，可以用pair合并，first是身高，second是相同个数，显然相同的数只会有一个，因为每一次操作，栈中相同数都已经合并完了。
我们再来透彻的理解一下单调栈。当 \(a_i\) 破坏单调性之后，显然，栈之前有一部分元素小于 \(a_i\) 。那么这些小于 \(a_i\) 的元素都会被 \(a_i\) 看到，所以这些元素都弹出，也都计入答案。
这时候我们就会有疑问了：弹出的数不会影响后面的结果吗？当然不会。题目是说 \(a_i\) 和 \(a_j\) 能互相看见当且仅当 \(a_k\le a_i,a_j, i<k<j\)。所以，如果一个数大于栈顶了，弹出之后满足单调性了，后面再来一个大数，它也并不能看到刚才弹出的数，如果后面来一个小数，那么更看不到之前的数了，所以不会影响。
然后这道题开个ll，然后注意相邻的人都是可以看到的。
#include <bits/stdc++.h>
#define rei register int
#define LL long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define cvar int n, m, T;
#define rep(i, s, n, c) for (register int i = s; i <= n; i+=c)
#define repd(i, s, n, c) for (register int i = s; i >= n; i-=c)
#define CHECK cout<<"WALKED"<<endl;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x*f;}
#define pb push_back
#define ls id<<1
#define rs id<<1|1
const int INF = INT_MAX;
long long binpow(long long a, long long b, LL mod){long long res = 1; while (b > 0){if (b & 1) res = res * a % mod;a = a * a % mod; b >>= 1; } return res;}
using namespace std;
stack<pair<LL, LL> >ddz;
LL h[500010], n, ans, cnt;
int main()
{
cin >> n;
rep (i, 1, n, 1) {
cin >> h[i];
}
rep (i, 1, n, 1) {
cnt = 0;
while (!ddz.empty() && ddz.top().first <= h[i]) {
if (ddz.top().first == h[i])
cnt = ddz.top().second;
ans += ddz.top().second;
ddz.pop();
}
if (!ddz.empty())
ans++;
ddz.push(make_pair(h[i], cnt + 1));
}
cout << ans << endl;
return 0;
}