题解 CF817D 【Imbalanced Array】

2020-02-22 02:25:02


首先,Orz DXL\ .

然后冷静分析,发现这是一道比较玄学的题目。

题目实际上是给定一个数组,求每一个区间的最大值最小值的差的总和。

然后 $\Theta(N^2logN)$水过。

对于1e6级别的数据,我们需要另辟蹊径:求贡献

我们可以发现,“求(每一个区间的最大值最小值的差)的总和”(括号代表断句),

可以转化为“求(每一个区间的最大值的总和)与(每一个区间的最小值的总和)的差”,

又可以转化为“求每一个数字作为最大值和最小值的次数,两者乘上权,再求差,再求和”。

然后问题就迎刃而解。

进入代码部分。

这道题是用单调栈来求贡献。这是一个相当经典的模型。

pic1

假如每个竖的线段的高度代表每一个数值,我们当前要求最大值得总和。那么我们需要考虑红的和绿的分别会作为哪些区间的最大值。

红:(2,2)

绿:(2,4)(3,4)(4,4)(2,5)(3,5)(4,5)

我们发现,作为区间最大值的区间数量其实就是

到左边“靠山”的距离 乘上 到右边的“靠山”的距离。

pic2

读者自证不难。同时,对于求最小值总和,由于不方便形象举例,读者自行推导(反正就是大小于号换一下)。

代码

加一的细节卡了我好久,希望大家注意一下。

需要注意的是,如果所有元素都遍历完了,还有元素在单调栈里,我们需要在 $n+1$的位置放一个“巨型靠山”,否则会出错。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1050005;
int n,st[N],a[N],b[N],pos[N],top=0;
int ans=0;
int sum_max,sum_min;
int Left[N],Right[N];
signed main(){
    cin>>n;
    for(int i=1;i<=n;++i)
        scanf("%lld",&a[i]);
//--------------以下是计算最大值贡献--------------
    for(int i=1;i<=n;++i){
        while(top!=0&&st[top]<a[i]){//单调栈的维护。st[]表示单调栈,存放元素的具体数值。top表示顶指针。 
            Right[pos[top]]=i-pos[top];//Right[]是右边的靠山。pos[i]表示st[i]的元素在a[]数组中的下标。 
            top--;
        }
        Left[i]=i-pos[top];//Left[]是左边的靠山。
        st[++top]=a[i];//元素入栈 
        pos[top]=i;
    }
    while(top)//栈内剩余元素处理(巨型靠山)
        Right[pos[top]]=n+1-pos[top],top--;
    for(int i=1;i<=n;++i)//计算贡献 
        sum_max+=(a[i]*(Left[i])*(Right[i]));

//-----以下是计算最小值贡献(就minmax换一下,改个大小于号。具体的参考上面。 
    memset(Left,0,sizeof(Left));
    memset(Right,0,sizeof(Right));
    for(int i=1;i<=n;++i){
        while(top!=0&&st[top]>a[i]){
            Right[pos[top]]=i-pos[top];
            top--;
        }
        Left[i]=i-pos[top];
        st[++top]=a[i];
        pos[top]=i;
    }
    while(top)
        Right[pos[top]]=n+1-pos[top],top--;
    for(int i=1;i<=n;++i)
        sum_min+=(a[i]*(Left[i])*(Right[i]));

    cout<<sum_max-sum_min<<endl;//输出 
}

注释都在上面了。有问题可以博客提问,或者私信提问!

鸣谢

感谢洛谷提供评测和博客服务。

感谢ISP项目组提供私人图床服务。