题目背景
为避免卡常,本题时限为比赛时的 2 倍。
你试过用笔记本的触摸板操作扒谱吗?
阿绫正在玩天依——最新的 X Studio 声库,由于触控板和鼠标神秘失踪,她每调整一个音符都极其费力……
题目描述
在阿绫正在调的序列中一共有 n 个音符,从左至右第 i 个音符的音高为 si。阿绫发现其中三个音符 si,sj,sk (1≤i<j<k≤n) 产生的听感不佳,她决定将它们调整为 si′,sj′,sk′,使得 si′≤sk′ 且 sj′≤sk′。扒拉触摸板真的很难受:
- 调节 si 到 si′ 需要耗费阿绫 a×∣si−si′∣ 的精力;
- 调节 sj 到 sj′ 需要耗费阿绫 b×∣sj−sj′∣ 的精力;
- 调节 sk 到 sk′ 需要耗费阿绫 c×∣sk−sk′∣ 的精力。
于是,调节完这三个音符,阿绫耗费的精力为:
$$z=a\cdot|s_i-s_i'|+b\cdot|s_j-s_j'|+c\cdot|s_k-s_k'|.
$$
阿绫自然会找到使得 z 值最小的 (si′,sj′,sk′),记此时的 z 值为 f(i,j,k)。现在阿绫想知道,对于所有满足 i<j<k 的 (i,j,k),f(i,j,k) 之和是多少呢?你只需要回答她这一答案对 232 取模的结果。
输入格式
第一行一个整数 n 表示音符序列的长度。
第二行三个整数 a,b,c。
第三行 n 个整数表示 s 序列,也就是每个音符的音高。
输出格式
一行一个整数即答案。
4
3 4 5
2 4 3 1
39
提示
样例解释
f(1,2,3)=4,其中一组最优的 (si′,sj′,sk′) 为 (2,3,3)。
f(1,2,4)=13,其中一组最优的 (si′,sj′,sk′) 为 (2,2,2)。
f(1,3,4)=9,其中一组最优的 (si′,sj′,sk′) 为 (2,2,2)。
f(2,3,4)=13,其中一组最优的 (si′,sj′,sk′) 为 (3,3,3)。
f(i,j,k) 的总和为 4+13+9+13=39。
数据规模与约定
本题采用捆绑测试。 仅当你通过了该子任务的全部测试数据才能获得该子任务的分值。
对于 100% 的数据,3≤n≤5×105,1≤si,a,b,c≤109。
对于不同的子任务,作如下约定:
子任务编号 |
n |
特殊性质 |
子任务分值 |
1 |
=3 |
无 |
5 |
2 |
≤300 |
3 |
≤1000 |
10 |
4 |
≤5×103 |
20 |
5 |
≤5×104 |
6 |
≤5×105 |
有 |
7 |
无 |
特殊性质:出现的不同音高不超过 10 种。