「eJOI2021」做题记录

加K

首先看查询操作，设 $$B_n=\sum_{i=1}^n A_i,C_i=\sum_{i=1}^ni\times A_i$$ 那么对于 \(r-l+1 < m\) ，显然有 \(f(l,r,m)=0\) 。否则拆贡献，可以看作 $$f(l,r,m)=\sum_{i=l}^{r-m+1}\sum_{j=i}^{i+m-1}A_i\\ =m\sum_{i=l}^r A_i-\sum_{i=l}^{l+m-1}(l+m-1-i)A_i+\sum_{i=r-m+1}^{r}(i-(r-m+1))A_r\\ =m\times sumB(l,r)-(l+m-1)\times sumB(l,l+m-1)+(r-m+1)\times sumB(r-m+1,r)+sumC(l,l+m-1)-sumC(r-m+1,r)\\ $$ 树状数组维护 \(B,C\) 即可。

K 划分

由定义，一个长度为 \(K\) 的区间可以被划分，当且仅当这一段的和 \(S\) 为偶数且可以取出一些数满足和为 \(S/2\) 。我们记 \(dp[i]\) 为最右的位置使得存在从该位置开始的一个子序列和为 \(i\) 。当我们考虑到 \(A_n\) 时，有转移： $$dp[v+A[i]]=\max(dp[v+A[i]],dp[v])$$ 每次更新后，我们对于当前可能的所有 \(K\) 分别判定即可。总时间复杂度是 \(O(\frac{N\sum{A_i}}{2})\) 的。