[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;
}

原文地址：http://www.cnblogs.com/CYLSY/p/16815983.html