洛谷P1823 [COI2007] Patrik 音乐会的等待

题目描述

N个人正在排队进入一个音乐会。人们等得很无聊，于是他们开始转来转去，想在队伍里寻找自己的熟人。队列中任意两个人A和B，如果他们是相邻或他们之间没有人比A或B高，那么他们是可以互相看得见的。

写一个程序计算出有多少对人可以互相看见。

输入格式

输入的第一行包含一个整数N (1 ≤ N ≤ 500 000), 表示队伍中共有N个人。

接下来的N行中，每行包含一个整数，表示人的高度，以毫微米(等于10的-9次方米)为单位，每个人的调度都小于2^31毫微米。这些高度分别表示队伍中人的身高。

输出格式

输出仅有一行，包含一个数S，表示队伍中共有S对人可以互相看见。

题解：首先我们不难想到一种O(n²)的算法，就是让每个人在队伍中找他能看到的人，最后答案就是找到的总人数除以2，显然这样会TLE，

我们考虑一下，因为要找几对能看到的人，我们不妨就找某个人前面自己能看到的人，显然这样能找到最优解，我们可以维护一个单调递减

的栈，某个元素它最少看到一个人，最多看到栈内比自己小的元素加1个人，这样可以实现，但此题经过数据加强，这样的算法竟也TLE了。

所以我们再用二分查找加速一下。

//80

 1 // luogu-judger-enable-o2
 2 #include<cstdio>
 3 #include<iostream>
 4 #include<cstring>
 5 #include<algorithm>
 6 
 7 using namespace std;
 8 
 9 int s[500005],top,n,h,res;
10 
11 int main()
12 {
13     scanf("%d",&n);
14     for(int i=1;i<=n;i++)
15     {
16         scanf("%d",&h);
17         while(s[top]<h&&top>0) top--,res++;
18         int j=0;
19         while(s[top]==h&&top>0) top--,res++,j++;
20         if(top!=0) res++;
21         top+=j;
22         s[++top]=h;
23     }
24     printf("%d
",res);
25     return 0;
26 }

//100

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <stack>

using namespace std;

typedef long long llint;
typedef pair<int,int> par;

stack<par> S;

int main( void ) {
   int n;
   scanf( "%d", &n );

   llint ret = 0;
   for( int i = 0; i < n; ++i ) {
      int h;
      scanf( "%d", &h );

      par p( h, 1 );
      for( ; !S.empty() && S.top().first <= h; S.pop() ) {
         ret += S.top().second;
         if( S.top().first == h ) p.second += S.top().second;
      }

      if( !S.empty() ) ++ret;
      S.push( p );
   }

   cout << ret << endl;

   return 0;
}