7205 - 划分
2048 年，第三十届CSP认证的考场上，作为选手的小明打开了第一题。这个题的样例有 n 组数据，数据从 1∼n 编号，i 号数据的规模为 ai。
小明对该题设计出了一个暴力程序，对于一组规模为 u 的数据，该程序的运行时间为 u的平方。然而这个程序运行完一组规模为 u 的数据之后，它将在任何一组规模小于 u 的数据上运行错误。样例中的 ai 不一定递增，但小明又想在不修改程序的情况下正确运行样例，于是小明决定使用一种非常原始的解决方案：将所有数据划分成若干个数据段，段内数据编号连续，接着将同一段内的数据合并成新数据，其规模等于段内原数据的规模之和，小明将让新数据的规模能够递增。
也就是说，小明需要找到一些分界点1≤k1<k2<⋯<kp<n，使得
注意 p 可以为 0 且此时 k0=0，也就是小明可以将所有数据合并在一起运行。
小明希望他的程序在正确运行样例情况下，运行时间也能尽量小，也就是最小化
小明觉得这个问题非常有趣，并向你请教：给定n和ai，请你求出最优划分方案下，小明的程序的最小运行时间。
输入
由于本题的数据范围较大，部分测试点的 ai 将在程序内生成。 第一行两个整数 n,type。n 的意义见题目描述， type 表示输入方式。
- 若 type=0，则该测试点的ai 直接给出。输入文件接下来：第二行 n 个以空格分隔的整数 ai，表示每组数据的规模。
- 若 type=1，则该测试点的 ai 将特殊生成，生成方式见后文。输入文件接下来：第二行六个以空格分隔的整数 x,y,z,b1,b2,m。接下来 m 行中，第i(1≤i≤m) 行包含三个以空格分隔的正整数 pi,li,ri。 对于 type=1 的 23~25 号测试点，ai 的生成方式如下： 给定整数x,y,z,b1,b2,m，以及 m 个三元组 (pi,li,ri)。 保证 n≥2。若 n>2，则 ∀3≤i≤n,bi=(x×bi−1+y×bi−2+z)mod2的30次方。 保证 1≤pi≤n,pm=n。令 p0=0，则 pi 还满足 ∀0≤i<m 有pi<pi+1。 对于所有 1≤j≤m，若下标值 i(1≤i≤n)满足pj−1<i≤pj，则有ai=(bimod(rj−lj+1))+lj 上述数据生成方式仅是为了减少输入量大小，标准算法不依赖于该生成方式。
输出
输出一行一个整数，表示答案。
样例
输入
5 0 5 1 7 9 9
输出
247
输入
10 0 5 6 7 7 4 6 2 13 19 9
输出
1256
输入
10000000 1 123 456 789 12345 6789 3 2000000 123456789 987654321 7000000 234567891 876543219 10000000 456789123 567891234
输出
4972194419293431240859891640
提示
【样例 1 解释】 最优的划分方案为 {5,1},{7},{9},{9}{5,1},{7},{9},{9}。由 5+1≤7≤9≤9 知该方案合法。 答案为 （5+1）的平方+7的平方+9的平方+9的平方=247。 虽然划分方案{5},{1},{7},{9},{9} 对应的运行时间比 247 小，但它不是一组合法方案，因为 5>1。 虽然划分方案 {5},{1,7},{9},{9}{5},{1,7},{9},{9} 合法，但该方案对应的运行时间为 251，比 247 大。 【样例 2 解释】 最优的划分方案为 {5},{6},{7},{7},{4,6,2},{13},{19,9}。
来源
CSP