题目背景

小Z最擅长解决序列问题啦，什么最长公共上升然后下降然后上升的子序列，小Z都是轻松解决的呢。

但是小Z不擅长出序列问题啊，所以它给了你一道签到题。

题目描述

给定一个n个数的序列ai，你要求出满足下述条件的点对的数量。

假设点对是(i , j)，max(l,r)是[l,r]当中最大的ai的值。

这个点对满足条件当且仅当i+1<j 且 ai < max(i+1,j-1) < aj

为了简单，保证输入的是一个1-n的排列。相信你已经会做了吧？

输入输出格式

输入格式：

 

输入数据第一行有一个数字n，然后第二行有n个数。

 

输出格式：

 

输出仅包含一个数，表示满足条件的数对的数量。

 

输入输出样例

输入样例#1：

51 2 3 4 5

输出样例#1：

6

说明

样例中，满足条件的分别是(1,3),(1,4),(1,5),(2,4),(2,5),(3,5)

对于50%的数据，满足n<=300

对于95%的数据，满足n<=10000

对于100%的数据，满足n<=1000000

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;int read(){    int t=1,num=0;    char c=getchar();    while(c>'9'||c<'0'){
   if(c=='-')t=-1;c=getchar();}    while(c>='0'&&c<='9'){num=num*10+c-'0';c=getchar();}    return num*t;}const int maxn=1000010;int q[maxn],tot=0,n,zhi[maxn];long long ans=0;int main(){    n=read();    for(int i=1;i<=n;i++)zhi[i]=read();    for(int i=n;i;i--){        while(q[tot]<=zhi[i]&&tot)tot--;        q[++tot]=zhi[i];if(tot>=3)ans+=tot-2ll;    }    printf("%lld",ans);    return 0;}
        
       
      
     

本文由Yzyet编写，网址为www.cnblogs.com/Yzyet。非Yzyet同意，禁止转载，侵权者必究。