题目描述
给出一个长度为 \(n\) 的序列 \(a_i\)，求出下列式子的值：
\[\sum_{i=1}^n \sum_{j=i}^n (\max \limits_{i \le k \le j} a_k-\min \limits_{i \le k \le j}a_k) \]即定义一个子序列的权值为序列内最大值与最小值的差。求出所有连续子序列的权值和。
具体思路
暴力思路很好想，就是按照式子来打，然后区间最大值和区间最小值可以用数组预处理一下。
时间复杂度：\(O(n^2)\)。
那么我们发现，如果我们的两个求和不拆掉那么时间复杂度就不正确，那么思路就很显然：计算每个 \(a_i\) 算了多少遍。
可以考虑将 \(a_i\) 看成一个宽度为 \(1\)，高度为 \(a_i\) 的矩形。
如图所示，我们来考虑上图中红色部分作为最大值被计算了多少次。
-
当 \(i=2\)，当 \(j=3,4\) 时 \(a_3\) 被计算了一次。
-
当 \(i=3\)，当 \(j=3,4\) 时 \(a_3\) 被计算了一次。
那我们发现，\(i\) 这一层循环 \(a_k\) 被计算的次数是 \(k\) 到上一个比它大的位置，而 \(j\) 这一层循环 \(a_k\) 被计算的次数时 \(k\) 到下一个比它大的位置。
设 \(i\) 这层循环计算的次数是 \(l_k\)，\(j\) 这层循环计算的次数是 \(r_k\)。
\[ans=\sum_{k=1}^n l_k \times r_k \times a_k \]如果我们暴力枚举每一个点，然后暴力找上一个比它大的位置以及下一个比它大的位置，时间复杂度：\(O(n^2)\)。
这不没优化吗？
上面这个图，显然就很有单调栈的味道。
从左往右依次枚举每一个点，维护一个单调下降的栈，如果当前的点比栈顶要大，那么更新栈顶的信息，同时将栈顶踢出栈。
然后我们就愉快的解决了这个问题。
维护最小值也是同样的道理。
时间复杂度：\(O(n)\)。
Code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+5;
const int inf=0x3f3f3f3f;
int top,sta[N],l[N],r[N],a[N];
signed main(){
int n;scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&a[i]);
}
top=1;sta[top]=1;
l[1]=1;
for(int i=2;i<=n;i++){
while(top&&a[i]>a[sta[top]]){
r[sta[top]]=i-sta[top];
top--;
}
l[i]=i-sta[top];
sta[++top]=i;
}
a[n+1]=inf;
while(top&&a[n+1]>a[sta[top]]){
r[sta[top]]=n+1-sta[top];
top--;
}
int maxn=0;
for(int i=1;i<=n;i++){
maxn=maxn+l[i]*r[i]*a[i];
}
top=1;sta[top]=1;
l[1]=1;
for(int i=2;i<=n;i++){
while(top&&a[i]<a[sta[top]]){
r[sta[top]]=i-sta[top];
top--;
}
l[i]=i-sta[top];
sta[++top]=i;
}
a[n+1]=0;
while(top&&a[n+1]<a[sta[top]]){
r[sta[top]]=n+1-sta[top];
top--;
}
int minn=0;
for(int i=1;i<=n;i++){
minn=minn+l[i]*r[i]*a[i];
}
printf("%lld",maxn-minn);
return 0;
}