题解 CF817D 【Imbalanced Array】
Algha_Porthos
2020-02-22 02:25:02
首先，Orz _DXL\_ .
然后冷静分析,发现这是一道比较玄学的题目。
**题目实际上是给定一个数组，求每一个区间的最大值最小值的差的总和。**
~~然后$\Theta(N^2logN)$水过。~~
对于1e6级别的数据，我们需要另辟蹊径：**求贡献**。
我们可以发现，“求（每一个区间的最大值最小值的差）的总和”（括号代表断句），
可以转化为“求（每一个区间的最大值的总和）与（每一个区间的最小值的总和）的差”，
又可以转化为“求每一个数字作为最大值和最小值的次数，两者乘上权，再求差，再求和”。
然后问题就迎刃而解。
进入代码部分。
这道题是用单调栈来求贡献。这是一个相当经典的模型。
假如每个竖的线段的高度代表每一个数值，我们当前要求最大值得总和。那么我们需要考虑红的和绿的分别会作为哪些区间的最大值。
红：(2,2)
绿：(2,4)(3,4)(4,4)(2,5)(3,5)(4,5)
我们发现，作为区间最大值的区间数量其实就是
到左边“靠山”的距离 乘上 到右边的“靠山”的距离。
读者自证不难。同时，对于求最小值总和，由于不方便形象举例，读者自行推导（反正就是大小于号换一下）。
## 代码
加一的细节卡了我好久，希望大家注意一下。
需要注意的是，如果所有元素都遍历完了，还有元素在单调栈里，我们需要在$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项目组提供私人图床服务。