7.25某题总结

· · 个人记录

对于一个m，我们假定t为负数的分界线，t及t左边的负数放在第一块，t右边的负数和正数放在最后一块

此时的和为

\sum^t_{i=1}(a_i+1)^2+\sum_{i=t+1}^n(a_i+m)^2

众多周知，

(a+b)^2 = a^2+b^2+2ab

所以

\sum_{i=1}^t(a_i^2+2a_i+1)+\sum_{i=t+1}^{n}(a_i^2+2ma_i+m^2) (\sum_{i=1}^t a_i^2+2\sum_{i=1}^t a_i+t)+(\sum_{i=t+1}^{n}a_i^2+2m\sum_{i=t+1}^{n}a_i+\sum_{i=t+1}^{n}m^2) \sum_{i=1}^na_i^2+2\sum_{i=1}^{t}a_i+t+2m\sum_{i=t+1}^{n}a_i+(n-t)m^2

用sum代表前缀和，sum1代表平方的前缀和，于是它变成了这样：

sum1_n+2sum_t+t+2m(sum_n-sum_t)+(n-t)m^2)

由于题目说的是让你求m=1\sim k中所有的答案，而m越大，负数就越有可能跑到右边去，而t也就要么往左走，要么不动。所以在m为1的时候算一遍答案，记录下来，然后根据结论不停地左移，找到最大值，这样总共是O(k)的。(理论上指针是O(n)的，因为指针最多移动n格，但由于循环了k次，所以就算不移动，那也要计算进去，所以是整体是O(k)的)