题目描述
N个人正在排队进入一个音乐会。人们等得很无聊，于是他们开始转来转去，想在队伍里寻找自己的熟人。队列中任意两个人A和B，如果他们是相邻或他们之间没有人比A或B高，那么他们是可以互相看得见的。
写一个程序计算出有多少对人可以互相看见。
输入输出格式
输入格式：
输入的第一行包含一个整数N (1 ≤ N ≤ 500 000), 表示队伍*有N个人。
接下来的N行中，每行包含一个整数，表示人的高度，以毫微米(等于10的-9次方米)为单位，每个人的调度都小于2^31毫微米。这些高度分别表示队伍中人的身高。
输出格式：
输出仅有一行，包含一个数S，表示队伍*有S对人可以互相看见。
输入输出样例
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
#include<bits/stdc++.h>
using namespace std; stack<long long>stk;//存元素
stack<long long>num;//存相同元素数量 （两个栈同步）
| stk | 9 | 6 | （栈顶） |
| num | 3 | 2 | （栈顶） |
| 备注 | （栈中有·3个9） | （2个6） |
int n;
long long ans,tmp; //ans 累加器 int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%lld",&tmp);
while(!stk.empty() && stk.top() < tmp) //如果栈不为空 且栈顶元素比tmp小 那么看得到栈顶元素
{
stk.pop();
ans += num.top();
num.pop();
}
if(stk.empty())//若元素栈是空的 直接塞进去就好了
{
stk.push(tmp);
num.push();
}else//栈不是空的
{
if(tmp != stk.top())//栈顶元素与读到的元素不相同的情况
{
ans+=;//两人紧挨 肯定能看得到对方 故 累加器加1
stk.push(tmp);
num.push();
}else//栈顶元素与读到的元素相同的时候
if(stk.size() == ) //仅有一个元素
{
ans+=num.top();
int u = num.top();
num.pop();
num.push(u+);
}
else//栈顶元素与读到的元素相同的时候 且 有多个元素
{
ans += num.top();
int u = num.top();
num.pop();
ans += ;
num.push(u+);
}
}
}
printf("%lld\n",ans);
return ;
}
分情况讨论
（1）.栈为空：直接把新元素压入就好
（2）.栈不为空：1.栈顶元素<tmp
栈顶元素都看得到
累加器+=栈顶元素个数
弹出栈顶元素
2.栈顶元素=tmp
<1> 栈中仅有一个元素
都看得到
stk不变； tmp的值（唯一的元素的值）+1
<2>栈中仍有多个元素
都看得到
stk不变； tmp的值（唯一的元素的值）+1
同时也相当于与相邻元素紧挨 ans+1
3.栈顶元素>tmp
由于紧挨着 ans+1
备注：
1.从上到下依次特判 调整顺序不可以
2.开long long
3.注意ans是+1还是+num.tpo();