前往：我自己搭建的博客
题目
洛谷P1823[COI2007]Patrik音乐会的等待
题解
使用单调栈维护一个不严格递减的数列，将新的元素与栈顶元素依次比较，如果符合要求（能互相看到）就计数，同时维护栈内数据的性质。计数时细节较多：题中要求多少对人，所以在对新元素进行处理时，只需要统计他左边能互相看到的人；多个连续的高度相同的人能互相看到；相邻的人能互相看到；相邻且高度相同的人只要统计一次。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
ll ans;
stack<pair<int,int> > s; //高度/此高度的人的数量
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int t; scanf("%d",&t);
while(s.size()&&s.top().first<t) ans+=s.top().second,s.pop();
if(s.size()&&s.top().first==t) ans+=s.top().second++;
else s.push(make_pair(t,1));
if(s.size()>=2) ans++; //统计左侧第一个比他高的人
}
printf("%lld\n",ans);
return 0;
}
