#P11771. 调的啥啊

    ID: 11412 远端评测题 2000ms 512MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>线段树洛谷原创O2优化容斥原理洛谷月赛

调的啥啊

题目背景

为避免卡常,本题时限为比赛时的 2 倍。

你试过用笔记本的触摸板操作扒谱吗?

阿绫正在玩天依——最新的 X Studio 声库,由于触控板和鼠标神秘失踪,她每调整一个音符都极其费力……

题目描述

在阿绫正在调的序列中一共有 nn 个音符,从左至右第 ii 个音符的音高为 sis_i。阿绫发现其中三个音符 si,sj,sk (1i<j<kn)s_i,s_j,s_k~(1\le i<j<k\le n) 产生的听感不佳,她决定将它们调整为 si,sj,sks_i',s_j',s_k',使得 sisks_i'\le s_k'sjsks_j'\le s_k'。扒拉触摸板真的很难受:

  • 调节 sis_isis_i' 需要耗费阿绫 a×sisia\times|s_i-s_i'| 的精力;
  • 调节 sjs_jsjs_j' 需要耗费阿绫 b×sjsjb\times|s_j-s_j'| 的精力;
  • 调节 sks_ksks_k' 需要耗费阿绫 c×skskc\times|s_k-s_k'| 的精力。

于是,调节完这三个音符,阿绫耗费的精力为:

$$z=a\cdot|s_i-s_i'|+b\cdot|s_j-s_j'|+c\cdot|s_k-s_k'|. $$

阿绫自然会找到使得 zz 值最小的 (si,sj,sk)(s_i',s_j',s_k'),记此时的 zz 值为 f(i,j,k)f(i,j,k)。现在阿绫想知道,对于所有满足 i<j<ki<j<k(i,j,k)(i,j,k)f(i,j,k)f(i,j,k) 之和是多少呢?你只需要回答她这一答案对 2322^{32} 取模的结果。

输入格式

第一行一个整数 nn 表示音符序列的长度。

第二行三个整数 aabbcc

第三行 nn 个整数表示 ss 序列,也就是每个音符的音高。

输出格式

一行一个整数即答案。

4
3 4 5
2 4 3 1
39

提示

样例解释

f(1,2,3)=4f(1,2,3)=4,其中一组最优的 (si,sj,sk)(s_i',s_j',s_k')(2,3,3)(2,3,3)

f(1,2,4)=13f(1,2,4)=13,其中一组最优的 (si,sj,sk)(s_i',s_j',s_k')(2,2,2)(2,2,2)

f(1,3,4)=9f(1,3,4)=9,其中一组最优的 (si,sj,sk)(s_i',s_j',s_k')(2,2,2)(2,2,2)

f(2,3,4)=13f(2,3,4)=13,其中一组最优的 (si,sj,sk)(s_i',s_j',s_k')(3,3,3)(3,3,3)

f(i,j,k)f(i,j,k) 的总和为 4+13+9+13=394+13+9+13=39

数据规模与约定

本题采用捆绑测试。 仅当你通过了该子任务的全部测试数据才能获得该子任务的分值。

对于 100%100\% 的数据,3n5×1053\le n\le5\times10^51si,a,b,c1091\le s_i,a,b,c\le 10^9

对于不同的子任务,作如下约定:

子任务编号 nn 特殊性质 子任务分值
11 =3=3 55
22 300\le300
33 1000\le1000 1010
44 5×103\le5\times10^3 2020
55 5×104\le5\times10^4
66 5×105\le5\times10^5
77

特殊性质:出现的不同音高不超过 1010 种。