Minimum Sum （单调栈）_综合

Minimum Sum （ AtCoder - agc005_b ）

Problem Statement

One day, Snuke was given a permutation of length N, a1,a2,…,aN, from his friend.

Find the following:
在这里插入图片描述

Constraints

1≦N≦200,000
(a1,a2,…,aN) is a permutation of (1,2,…,N).

Input

The input is given from Standard Input in the following format:
N
a1 a2 … aN

Output

Print the answer.

Note that the answer may not fit into a 32-bit integer.

Sample Input 1

3
2 1 3

Sample Output 1

Sample Input 2

4
1 3 2 4

Sample Output 2

Sample Input 3

8
5 4 8 1 2 6 7 3

Sample Output 3

在这里插入图片描述

由题意可以知道，需要求出每一个数所对应的最大左边界和最大右边界，因此可以维护一个单调递增栈，求出每个数所对应的左右边界L [ N ] 和 R [ N ]
( i - l [ i ] ) * ( r [ i ] - i ) 子区间的数量

AC代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
using namespace std;
typedef long long ll;
const int N=200010;
ll n;
ll p[N];
ll top;
struct St{
    ll num;ll id;
}st[N];
ll l[N],r[N]; int main()
{
    cin>>n;for(int i=1;i<=n;i++){
    cin>>p[i];l[i]=0;r[i]=n+1;}for(int i=1;i<=n;i++){
    while(top&&st[top].num>=p[i]) --top;if(top) l[i]=st[top].id;st[++top].num=p[i];st[top].id=i;}top=0;for(int i=n;i>=1;i--){
    while(top&&st[top].num>=p[i]) --top;if(top) r[i]=st[top].id;st[++top].num=p[i];st[top].id=i;}ll ans=0;for(int i=1;i<=n;i++){
    ans+=p[i]*(i-l[i])*(r[i]-i);}cout<<ans<<endl;return 0;	
}

Minimum Sum （ 单调栈 ）