P5665 [CSP-S 2019] Partition

In 2048, at the exam site of the 30th CSP certification, contestant Xiaoming opened the first problem. The sample of this problem has $n$ groups of testdata, numbered from $1 \sim n$, and the size of the $i$-th testdata is $a_i$. Xiaoming designed a brute-force program for this problem. For a piece of testdata of size $u$, the **running time** of the program is $u^2$. However, after the program finishes running on a piece of testdata of size $u$, it will produce wrong results on any piece of testdata whose size is **less than** $u$. The $a_i$ in the sample are not necessarily increasing, but Xiaoming wants to run the sample correctly without modifying the program. So he decided to use a very primitive solution: divide all testdata into several segments, where the indices within each segment are **continuous**. Then, merge the testdata within the same segment into new testdata whose size equals the **sum of sizes** of the original testdata in that segment. Xiaoming will make the sizes of the new testdata non-decreasing. That is, Xiaoming needs to find some split points $1 \leq k_1 \lt k_2 \lt \cdots \lt k_p \lt n$ such that $$ \sum_{i=1}^{k_1} a_i \leq \sum_{i=k_1+1}^{k_2} a_i \leq \cdots \leq \sum_{i=k_p+1}^{n} a_i $$ Note that $p$ can be $0$, and in this case $k_0 = 0$, meaning Xiaoming can merge all testdata together and run it once. Xiaoming hopes that, while running the sample correctly, the running time can be as small as possible, i.e., **minimize**: $$ \left(\sum_{i=1}^{k_1} a_i\right)^2 + \left(\sum_{i=k_1+1}^{k_2} a_i\right)^2 + \cdots + \left(\sum_{i=k_p+1}^{n} a_i\right)^2 $$ Xiaoming finds this problem very interesting and asks you for help: given $n$ and $a_i$, please compute the minimum running time of Xiaoming's program under the optimal partition.

**Because the Constraints of this problem are large, for some test points, $a_i$ will be generated inside the program.** The first line contains two integers $n, type$. The meaning of $n$ is described above, and $type$ indicates the input method. 1. If $type = 0$, then $a_i$ for this test point are **given directly**. The input then contains: on the second line, $n$ integers $a_i$ separated by spaces, representing the size of each group of testdata. 2. If $type = 1$, then $a_i$ for this test point will be **generated specially**; the generation method is given later. The input then contains: on the second line, six integers $x, y, z, b_1, b_2, m$ separated by spaces. In the next $m$ lines, the $i$-th line $(1 \leq i \leq m)$ contains three positive integers $p_i, l_i, r_i$ separated by spaces. For test points $23 \sim 25$ with $type = 1$, $a_i$ are generated as follows: Given integers $x, y, z, b_1, b_2, m$, and $m$ triples $(p_i, l_i, r_i)$. It is guaranteed that $n \geq 2$. If $n \gt 2$, then for all $3 \leq i \leq n$, $b_i = (x \times b_{i−1} + y \times b_{i−2} + z) \bmod 2^{30}$. It is guaranteed that $1 \leq p_i \leq n$ and $p_m = n$. Let $p_0 = 0$, then $p_i$ also satisfies: for all $0 \leq i \lt m$, $p_i \lt p_{i+1}$. For all $1 \leq j \leq m$, if the index $i (1 \leq i \leq n)$ satisfies $p_{j−1} \lt i \leq p_j$, then $$a_i = \left(b_i \bmod \left( r_j − l_j + 1 \right) \right) + l_j$$ **The above data generation method is only to reduce the input size; the standard algorithm does not depend on this generation method.**

Output one integer in one line, representing the answer.

[Sample 1 Explanation] The optimal partition is $\{5,1\}, \{7\}, \{9\}, \{9\}$. Since $5 + 1 \leq 7 \leq 9 \leq 9$, this partition is valid. The answer is $(5 + 1)^2 + 7^2 + 9^2 + 9^2 = 247$. Although the partition $\{5\}, \{1\}, \{7\}, \{9\}, \{9\}$ has a running time smaller than $247$, it is not valid because $5 \gt 1$. Although the partition $\{5\}, \{1,7\}, \{9\}, \{9\}$ is valid, its running time is $251$, which is larger than $247$. [Sample 2 Explanation] The optimal partition is $\{5\}, \{6\}, \{7\}, \{7\}, \{4,6,2\}, \{13\}, \{19,9\}$. [Constraints] ::cute-table[]{tuack} | Test Point ID | $n \leq$ | $a_i \leq$ | $type =$ | | :--: | :-: | :-: | :-: | | $1 \sim 3$ | $10$ | $10$ | $0$ | | $4 \sim 6$ | $50$ | $10^3$ | ^ | | $7 \sim 9$ | $400$ | $10^4$ | ^ | | $10 \sim 16$ | $5000$ | $10^5$ | ^ | | $17 \sim 22$ | $5 \times 10^5$ | $10^6$ | ^ | | $23 \sim 25$ | $4 \times 10^7$ | $10^9$ | $1$ | For all test points with $type=0$, it is guaranteed that the final output answer $\leq 4 \times 10^{18}$. All test points satisfy: $type \in \{0,1\}$, $2 \leq n \leq 4 \times 10^7$, $1 \leq a_i \leq 10^9$, $1 \leq m \leq 10^5$, $1 \leq l_i \leq r_i \leq 10^9$, $0 \leq x,y,z,b_1,b_2 \lt 2^{30}$。 Translated by ChatGPT 5