题解 P6503 【[COCI2010-2011#3] DIFERENCIJA】

Alex_Wei · 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;
}