代码源每日一题div1 子串的最大差

子串的最大差 - 题目 - Daimayuan Online Judge

题意：定义序列的最大差为序列中最大数与最小数的差。比如 (3,1,4,5,6)的最大差为 6−1=5, (2,2)的最大差为 2−2=0。

定义一个序列的子串为该序列中连续的一段序列。

给定一个长度为 n 的数组 a1,a2,…,an，请求出这个序列的所有子串的最大差之和。

思路：

一开始的思路有3个：把最大差合并同类项，找出性质，或者遍历所有子串，用线段树维护区间最大值和区间最小值，或用线段树构造出所有子串（显然做不到）

显然不能遍历所有子串，直接超时

我们只需求出最大差之和，遍历会超时，鉴定为贡献题，我们更换枚举的对象为每个元素，考虑每个元素对最大差之和的贡献

对于每个元素，我们求出每个元素作为最大值和最小值的子串个数

现在问题转变成了如何维护每个元素作为最值的子串个数

以元素作为最大值为例，子串个数为后面相邻的比它小的个数*前面相邻的比它小的个数*a[i]

若该元素作为最小值，贡献（即字串个数）为后面相邻的比它大的个数*前面相邻的比它大的个数*a[i]

这就是单个元素的贡献，我们遍历整个数列统计所有元素的贡献即可

现在问题转变成，如何维护前（后）面相邻的比它大（小）的元素的个数

只需用单调栈维护前（后）面第一个比它小（大）的数的位置即可

Code：

#include 
using namespace std;
const int mxn=5e5+10;
#define int long long
int n;
int a[mxn],f1[mxn],f2[mxn],f3[mxn],f4[mxn];
stack<int> s1,s2,s3,s4;
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    for(int i=n;i>=1;i--){//后面大于a[i]
        while(!s1.empty()&&a[s1.top()]pop();
        f1[i]=s1.empty()?n-i+1:s1.top()-i;
        s1.push(i);
    }
    for(int i=n;i>=1;i--){//后面小于a[i]
        while(!s2.empty()&&a[s2.top()]>a[i]) s2.pop();
        f2[i]=s2.empty()?n-i+1:s2.top()-i;
        s2.push(i);
    }
    for(int i=1;i<=n;i++){//前面大于a[i]
        while(!s3.empty()&&a[s3.top()]<=a[i]) s3.pop();
        f3[i]=s3.empty()?i:i-s3.top();
        s3.push(i);
    }
    for(int i=1;i<=n;i++){//前面小于a[i]
        while(!s4.empty()&&a[s4.top()]>=a[i]) s4.pop();
        f4[i]=s4.empty()?i:i-s4.top();
        s4.push(i);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        ans+=f1[i]*f3[i]*a[i];
        //printf("%d %d\n",f1[i],f3[i]);
    }
    for(int i=1;i<=n;i++){
        ans-=f2[i]*f4[i]*a[i];
        //printf("%d %d\n",f2[i],f4[i]);
    }
    printf("%lld\n",ans);
    return 0;
}

总结：

思维：

求最大差之和，我们不必模拟，只求出最大差即可，因此考虑贡献

由于枚举子串超时，我们更换枚举对象，枚举对象为元素，然后再去考虑贡献，这个时候贡献就会好维护的多

当我们枚举超时时，我们考虑：

1.是否满足单调性？是否可以二分？

2.更换枚举对象

3.考虑枚举的量直接的关系，没有关系就试着观察性质，如果观察出关系，就可以减少几个枚举变量

算法：

什么时候使用单调栈：维护前（后）面第一个比它大（小）的位置

写法（以维护右边第一个大于a[i]的元素为例）：

for(int i=n;i>=1;i--){//后面大于a[i]
        while(!s1.empty()&&a[s1.top()]pop();
        f1[i]=s1.empty()?/*若不存在第一个大于，则用右边界维护区间*/n-i+1:/*这里写第一个大于的位置*/s1.top()-i;
        s1.push(i);
    }