P8118 "RdOI R3.5" Mystery

You are given a non-decreasing integer sequence $\{a_i\}$ of length $n$ and an integer $k$. We define the "difference measure" of two sequences $\{x_i\}, \{y_i\}$ of the same length $p$ as $F(x,y,p)=\sum_{i=1}^p |x_i-y_i|$. Now, for each integer $l \in [1,n]$, you need to construct a sequence $\{b_{l,i}\}$ of length $l$, such that for any $1\le i < l$, $b_{l,i+1}\ge b_{l,i}+k$, and $F(a_{[1\cdots l]},b_l,l)$ is minimized. Here, $a_{[1\cdots l]}$ denotes the prefix of $\{a_i\}$ with length $l$, i.e., $\{a_1,a_2,\cdots,a_l\}$. Note that $b_{l,i}$ does not have to be an integer.

The first line contains two integers $n, k$. The second line contains $n$ integers, representing $\{a_i\}$. The third line contains an integer $T$, which specifies the output mode. See the "Output Format" for details.

- If $T=0$, output $n$ integers, one per line. The integer on line $l$ represents $F(a_{[1\cdots l]},b_l,l)$. - If $T=1$, you only need to output one integer on a single line, which is $F(a,b_n,n)$.

### Sample Explanation #### Sample \#1 One possible construction is: $$ \begin{aligned} b_1&=\{2\}\\ b_2&=\{2,4\}\\ b_3&=\{1,3,5\}\\ b_4&=\{1,3,5,7\}\\ b_5&=\{0,2,4,6,8\}\\ \end{aligned} $$ #### Sample \#2 One possible construction is: $$ \begin{aligned} b_1&=\{1\}\\ b_2&=\{0,2\}\\ b_3&=\{0,2,4\}\\ b_4&=\{0,2,4,6\}\\ b_5&=\{-1,1,3,5,7\}\\ b_6&=\{-1,1,3,5,7,9\}\\ \end{aligned} $$ #### Sample \#3 Same as Sample \#2, except that $T=1$. You only need to output $F(a,b_6,6)=5$. ### Constraints and Notes $$ \def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|} \hline \textbf{subtask} & \textbf{Score} & \bm{{n\le}} & \bm{{T=}} & \bm{{k,a_i\le}} & \textbf{subtask dependencies}\cr\hline 1 & 30 & 100 & 0 & 100 & -\cr\hline 2 & 30 & 10^5 & 0 & 10^6 & 1\cr\hline 3 & 40 & 10^6 & 1 & 10^6 & -\cr\hline \end{array} $$ For $100\%$ of the testdata, $1\le n \le 10^6$, $1\le k,a_i\le 10^6$, and $T\in\{0,1\}$. Translated by ChatGPT 5