E、希望
线段树维护区间最小值，计算出数组中小于0的元素删除所需要的代价和删除后对答案的贡献，然后做一次01背包，
就是最后可以获得的值。
J、外挂
通过观察操作2的计算方法，容易发现，然后线段树维护区间和和区间平方和。
传递标记的时候，发现区间和和区间平方和存在关系式 %5E2%3D%5Csum_%7Bi%3D1%7D%5E%7Bn%7D%7B(a_i%5E2%2B2*a_i%2B1)%7D%3D%5Csum_%7Bi%3D1%7D%5E%7Bn%7Da_i%5E2%2B2*%5Csum_%7Bi%3D1%7D%5E%7Bn%7Da_i%2Bn)
然后每次先维护区间平方和再维护区间和就可以啦
https://ac.nowcoder.com/acm/contest/view-submission?submissionId=40773194
全部评论
(1) 回帖