526互联

codeforces-817 D. Imbalanced Array(单调栈）

发布时间 2023-07-13 11:38:02作者: kingqiao

image

题意：求数组中每个连续子序列的的最大值-最小值之和。
思路：题意可以理解为加上每一个序列的最大值，减去每一个序列的最小值。每个数都可以作为某一连续子序列的最大值和最小值，所以可以枚举每一个数作为最值的区间，暴力枚举时间复杂度过高，所以利用单调栈找出每个数左边或右边第一个比本身小的数，这样该数就是区间中最小的数。同理也可以找该数为最大数的区间。这里有个坑就是有可能答案会算重复。比如1 4 1，第一个1最为最小值的时候会算一个1 4 1，第三个1最为最小值的时候也会算一个1 4 1。只有我们用单调栈来求L【i】的时候保持左开右闭就可以保证只算一次。

点击查看代码 
#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+100;
int a[N],l[N],r[N];
stack<int> s;

int main(){
    ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
    int n;
    long long ans = 0;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++){
        while(!s.empty()&&a[s.top()]>a[i]) s.pop();
        if(s.empty()) l[i] = 1;
        else l[i] = s.top() + 1;
        s.push(i);
    }
    while(!s.empty())
        s.pop();
    for(int i=n;i>=1;i--){
        while(!s.empty()&&a[s.top()]>=a[i]) s.pop();
        if(s.empty()) r[i] = n;
        else r[i] = s.top() - 1;
        s.push(i);
    }
    while(!s.empty())
        s.pop();
    for(int i=1;i<=n;i++)
        ans -= 1LL * (i - l[i] + 1) * (r[i] - i + 1) * a[i];

    for(int i=1;i<=n;i++){
        while(!s.empty()&&a[s.top()]<a[i]) s.pop();
        if(s.empty()) l[i] = 1;
        else l[i] = s.top() + 1;
        s.push(i);
    }
    while(!s.empty())
        s.pop();
    for(int i=n;i>=1;i--){
        while(!s.empty()&&a[s.top()]<=a[i]) s.pop();
        if(s.empty()) r[i] = n;
        else r[i] = s.top() - 1;
        s.push(i);
    }
    for(int i=1;i<=n;i++)
        ans += 1LL * (i - l[i] + 1) * (r[i] - i + 1) * a[i];
    cout<<ans<<'\n';
    return 0;
}