自动搬运

查看原文

来自洛谷，原作者为

	Alex_Wei **

搬运于2025-08-24 22:21:25，当前版本为作者最后更新于2020-08-23 14:13:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题面传送门。

题意简述：给出 $n$ 和 $a_i$，求

$$\sum_{i=1}^n\sum_{j=i}^n\left(\max_{i\leq k\leq j}a_k-\min_{i\leq k\leq j}a_k\right) $$

提供一个不一样的思路。

我们设 $f_i/g_i$ 为以 $i$ 结尾的所有子序列的最大 / 最小值之和，那么答案为 $\sum f_i-g_i$。

考虑如何维护 $f,g$。

不妨设 $p_i<i$ 为满足 $a_{p_i}>a_i$ 的最大的 $p_i$（特别的，如果 $p_i$ 不存在则为 $0$），那么有转移方程 $f_i=f_{p_i}+a_i\times (i-p_i)$，$p_i$ 可以用单调栈维护。

稍微解释一下上面的转移方程是如何得来的：

• 因为 $a_i$ 对 $p_i$ 以及 $p_i$ 以前的最大值没有影响（即 $[1,p_i]$ 与 $[1,i]$，$[2,p_i]$ 与 $[2,i]\cdots$ $[p_i,p_i]$ 与 $[p_i,i]$ 的最大值相同），所以可以直接由 $f_{p_i}$ 转移得来。
• 而根据 $p_i$ 的定义，后面 $i-p_i$ 个子序列（即 $[p_i+1,i],[p_i+2,i]\cdots,[i,i]$）的最大值为 $a_i$，所以加上 $a_i\times (i-p_i)$。
• 所以转移方程为 $f_i=f_{p_i}+a_i\times (i-p_i)$。

维护 $g$ 只需要将 $p_i$ 的定义中「$a_{p_i}>a_i$」改为「$a_{p_i}<a_i$」即可，用两个单调栈即可求出答案。

时间复杂度 $O(n)$，常数较小，代码好写，而且跑得飞快，甚至抢到了最优解（2020.8.23）。

const int N=3e5+5;

ll n,t1,t2,ans,f[N],g[N];
pii a[N],b[N];

int main(){
	n=read();
	for(int i=1;i<=n;i++){
		ll x=read(),p;
		while(t1&&x>=a[t1].fi)t1--;
		while(t2&&x<=b[t2].fi)t2--;
		p=a[t1].se; f[i]=f[p]+x*(i-p);
		p=b[t2].se; g[i]=g[p]+x*(i-p);
		ans+=f[i]-g[i],a[++t1]=b[++t2]={x,i};
	} cout<<ans<<endl;
	return 0;
}