题解 P6503 【[COCI2010-2011#3] DIFERENCIJA】

zpyyy · 2020-07-26 14:06:34 · 题解

事实上，本题要求的就是每个值作为最大值和最小值对答案有多少贡献
显然会有一个坑点，如果有一个区间里有两个相同的最大或最小值，但这个值对答案的贡献只能算做一次，所以可以把相同的数看成越前面（越后面）的越大
众所周知，部分单调栈的题目也可以使用链表
所以直接链表搞一搞就行了，显然不需要set这种常数极大的东东
Code:

#include<bits/stdc++.h>
#define ll long long
#define make(aa,bb) make_pair(aa,bb)
#define PII pair<int,int>
#define fi first
#define se second
#define lowbit(x) (x)&(-x)
#pragma GCC optimize(2)
using namespace std;
const int N=3e5+5;
ll a[N],le[N],ri[N];
ll ans;
int n,top;
int s[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);a[n+1]=a[0]=-1;
    le[1]=0,ri[n]=n+1;
    for(int i=1;i<=n;i++){
        int j=i-1;
        while(j){
            if(a[j]<=a[i]) j=le[j];
            else break;
        }
        le[i]=j;
    }
    for(int i=n;i>=1;i--){
        int j=i+1;
        while(j<=n){
            if(a[j]<a[i]) j=ri[j];
            else break;
        }
        ri[i]=j;
    }
    for(int i=1;i<=n;i++) ans+=(ll)(ri[i]-i)*(i-le[i])*a[i];
    memset(le,0,sizeof(le));
    memset(ri,0,sizeof(ri));
    le[1]=0,ri[n]=n+1;
    for(int i=1;i<=n;i++){
        int j=i-1;
        while(j){
            if(a[j]>=a[i]) j=le[j];
            else break;
        }
        le[i]=j;
    }
    for(int i=n;i>=1;i--){
        int j=i+1;
        while(j<=n){
            if(a[j]>a[i]) j=ri[j];
            else break;
        }
        ri[i]=j;
    }
    for(int i=1;i<=n;i++) ans-=(ll)(ri[i]-i)*(i-le[i])*a[i];
    printf("%lld",ans);
    return 0;
}