题目描述

A group of people are standing in a line. Each person has a distinct height. You would like to count the number of unordered pairs of people in the line such that they are taller than everyone in between them in the line.
More formally, let d be a sequence of the heights of the people in order from left to right. We want to count the number of pairs of indices i and j with i < j such that for all k with i < k < j,di > dk and dj > dk . Note that if j = i + 1 (i.e., there are no k’s between i and j), it is trivially true.

输入

The first line of input contains an integer n (2 ≤ n ≤ 106 ), which is the number of people.
Each of the next n lines contains a single integer di (1 ≤ di ≤ n). These are the heights of the people in the group, in the order in which they’re standing. The sequence is guaranteed to be a permutation of the integers 1 through n.

输出

Output a single integer, which is the number of pairs of people who are taller than everyone between them.

样例输入 Copy

【样例1】
3
2
1
3
【样例2】
6
1
3
2
6
4
5

样例输出 Copy

【样例1】
3
【样例2】
7


求（i，j）点对的数量使得区间[i+1,j-1]的最大值小于val[i],val[j]

三元组（i，k, j)如果从最小值的位置k开始找区间，i，j的话，好像并没有一个合适的复杂度，，，
然后如果我们枚举j这个点，每次向左找i点，这样的话可以用单调栈维护区间最大值
看看a[j]这个点向左最多维护到的位置，然后计算贡献就可以了
具体操作：
维护一个单调递减的栈，如果新插入的元素大于栈顶就一直pop，ans++

考虑这种做法的正确性：

栈内一直是递减的元素，6，4，3，2，1
此时来了一个5
那么栈更新为6，5，
然后又来了一个7的话，会不会少算贡献，
比如 如果不pop的话 栈内元素是 6，4，3，2，1，5，7
7和4，3，2，1的贡献会不会少算，当然不会了
因为中间来了个5 ，然后5左边的所有的数就不能满足条件了（因为维护的是递减序列）

细节：
就是注意处理(i,j)相邻的情况


CODE：

int n,val[maxn],st[maxn],top,ans;
int main() {
    n=read(),st[0] = inf;
    rep(i,1,n) val[i] = read();
    for(int i=1 ; i<=n ; i++) {
        if(top==0) st[++top] = val[i];
        else if(val[i]<st[top]) st[++top] = val[i];
        else {
            while(val[i]>st[top]&&top>=2) top--,ans++;
            if(val[i]<st[top])   st[++top] = val[i];
            else    st[top] = val[i];   
        }
    }
    out(ans+n-1);
    return  0;
}

View Code