#P5632. [CSP-S2019] 划分

    ID: 4633 传统题 2000ms 1024MiB 尝试: 91 已通过: 15 难度: 9 上传者: 标签>难度分类省选/NOI-动态规划线性 DP排序与序列处理一维前缀和单调队列贪心消除被支配候选枚举与搜索路径恢复模拟与实现技巧高精度乘法高精度加法CF2600单调队列/单调栈优化

[CSP-S2019] 划分

[CSP-S 2019] 划分

题目描述

小明的程序处理规模为 uu 的数据需要 u2u^2 的时间,而且只能按照规模非递减的顺序处理各组数据。现有 nn 组数据,第 ii 组的规模为 aia_i。

将数据按原有顺序划分成若干非空连续段,每段合并成一组新数据。若分界点为 0=k0<k1<⋯<kq=n0=k_0<k_1<\cdots<k_q=n,第 jj 组新数据的规模为

sj=∑i=kj−1+1kjai.s_j=\sum_{i=k_{j-1}+1}^{k_j}a_i.

要求 s1≤s2≤⋯≤sqs_1\le s_2\le\cdots\le s_q。可以把全部数据合并成一组。求运行时间 ∑j=1qsj2\sum_{j=1}^{q}s_j^2 的最小值。

输入格式

第一行两个整数 n,typen,\mathrm{type},分别表示原数据组数和输入方式。

  • type=0\mathrm{type}=0 时,第二行直接给出 nn 个整数 aia_i。
  • type=1\mathrm{type}=1 时,第二行给出 x,y,z,b1,b2,mx,y,z,b_1,b_2,m,接下来 mm 行依次给出三元组 (pj,lj,rj)(p_j,l_j,r_j)。

当 type=1\mathrm{type}=1 时,给定 b1,b2b_1,b_2,对 3≤i≤n3\le i\le n 依次生成

bi=(xbi−1+ybi−2+z) mod 230.b_i=(x b_{i-1}+y b_{i-2}+z)\bmod 2^{30}.

其中 0=p0<p1<⋯<pm=n0=p_0<p_1<\cdots<p_m=n。当 pj−1<i≤pjp_{j-1}<i\le p_j 时,令

ai=(bi mod (rj−lj+1))+lj.a_i=\bigl(b_i\bmod(r_j-l_j+1)\bigr)+l_j.

输出格式

输出一行一个整数,表示最小运行时间。

样例 1

5 0
5 1 7 9 9
247

一种最优划分是 {5,1},{7},{9},{9}\{5,1\},\{7\},\{9\},\{9\},代价为 62+72+92+92=2476^2+7^2+9^2+9^2=247。每个数单独成段时,前两个段和为 5,15,1,违反非递减条件。划分为 {5},{1,7},{9},{9}\{5\},\{1,7\},\{9\},\{9\} 的代价为 251251。

样例 2

10 0
5 6 7 7 4 6 2 13 19 9
1256

一种最优划分是 {5},{6},{7},{7},{4,6,2},{13},{19,9}\{5\},\{6\},\{7\},\{7\},\{4,6,2\},\{13\},\{19,9\}。

样例 3

10000000 1
123 456 789 12345 6789 3
2000000 123456789 987654321
7000000 234567891 876543219
10000000 456789123 567891234
4972194419293431240859891640

样例 4 与 5

原赛选手附件中的文件分别是 partition/partition4.in、partition/partition4.ans,以及 partition/partition5.in、partition/partition5.ans。

数据范围

原赛题面规定 2≤n≤4×1072\le n\le4\times10^7,1≤ai≤1091\le a_i\le10^9,type∈{0,1}\mathrm{type}\in\{0,1\}。本地评测的直接输入另有 n=1n=1 的测点。

生成数据时,1≤m≤1051\le m\le10^5,1≤lj≤rj≤1091\le l_j\le r_j\le10^9,0≤x,y,z,b1,b2<2300\le x,y,z,b_1,b_2<2^{30}。

本地版本中,type=0\mathrm{type}=0 的答案不超过 4×10184\times10^{18}。

原赛测试点 nn 上限 aia_i 上限 type\mathrm{type}
1–3 1010 0
4–6 5050 10310^3
7–9 400400 10410^4
10–16 50005000 10510^5
17–22 5×1055\times10^5 10610^6
23–25 4×1074\times10^7 10910^9 1