【学习笔记】P8590 『JROI-8』这是新历的朝阳，也是旧历的残阳

比较有思维的一个数学题，写个笔记纪念一下。

显然，为了使 $\sum\limits_{i=1}^n a_i^2$ 最大，整数一定要放最后一段，即求 $\sum\limits_{i=1}^n (a_i+m)^2$，而负数需要分情况考虑，即放第一段还是最后一段，中间的 $m-2$ 是空段，只考虑 $1$ 和 $m$ 这两个极端情况。

可以设中间节点 $t$，$a_{i\in[1,t]}$ 变为 $(a_{i\in[1,t]}+1)^2$，而 $a_{i\in(t,n]}$ 变为 $(a_{i\in(t,n]}+m)^2$，即 $a_i$ 变为 $\max((a_i+1)^2,(a_i+m)^2)$，现求 $t$，即有 $t_{\max}$使得 $(a_{t_{\max}}+1)^2>(a_{t_{\max}}+m)^2$。

然后，通过 $t$ 求出 $q_j=\sum\limits_{i=1}^t (a_i+1)^2+\sum\limits_{i=t+1}^n (a_i+m)^2$。

若直接计算 $q_j=\sum\limits_{i=1}^t (a_i+1)^2+\sum\limits_{i=t+1}^n (a_i+m)^2$ 显然超时，考虑优化。

将 $\sum\limits_{i=1}^t (a_i+1)^2$ 展开，通过 $(x+y)^2=x^2+2xy+y^2$ 得：

$\sum\limits_{i=1}^t (a_i+1)^2=\sum\limits_{i=1}^t (a_i^2+2a_i+1)=\sum\limits_{i=1}^t a_i^2+2\sum\limits_{i=1}^t a_i+t$

将 $\sum\limits_{i=t+1}^n (a_i+m)^2$ 展开，通过 $(x+y)^2=x^2+2xy+y^2$ 得：

$\sum\limits_{i=t+1}^n (a_i+m)^2=\sum\limits_{i=t+1}^n (a_i^2+2a_im+m^2)=\sum\limits_{i=t+1}^n a_i^2+2\sum\limits_{i=t+1}^n a_im+m^2(n-t)$

则

$q_j=\sum\limits_{i=1}^t (a_i+1)^2+\sum\limits_{i=t+1}^n (a_i+m)^2=\sum\limits_{i=1}^t a_i^2+\sum\limits_{i=1}^t 2a+t+\sum\limits_{i=t+1}^n a_i^2+\sum\limits_{i=t+1}^n 2a_im+m^2(n-t)$

合并，得

$q_j=\sum\limits_{i=1}^na_i^2+2\sum\limits_{i=1}^ta_i+2m\sum\limits_{i=t+1}^n a_i+m^2(n-t)+t$

在输入时求出 $k\sum\limits_{i=1}^na_i^2$，即求出所有 $q_{j\in[1,k]}$ 的 $\sum\limits_{i=1}^na_i^2$ 的和，即 $\sum\limits_{j=1}^k{\sum\limits_{i=1}^na_i^2}$。

在 $m$ 单调递增时，$t$ 是始终是不上升的，即若 $m_i<m_j$，则 $t_i\ge t_j$，即原来的 $(a_k+m_i)^2$ 变为了 $(a_k+m_j)^2$，显然 $(a_k+m_i)^2<(a_k+m_j)^2$，即若原来的 $a_k=\max((a_k+1)^2,(a_k+m_i)^2)=(a_k+1)^2$，则现在对于 $a_k$，$(a_k+m_j)^2$ 比 $(a_k+m_i)^2$ 更容易成为 $a_{k\max}$，即 $t$ 更可能变小，放在最后一段的个数更可能变多。