题解：AT_arc066_d [ARC066F] Contest with Drinks Hard

· · 题解

首先思考不带修的做法，可以直接 DP。

设 f_i 表示考虑了前 i 个数的答案，容易写出转移式 f_i = \max(f_{i-1} , \frac{(i-j) \times (i-j+1)}{2} - (sum_i - sum_j) + f_j) ，其中 sum 表示 T 的前缀和。

你给里面拆出来之后就可以直接斜率优化，不带修就做完了。

考虑带修会有什么影响。

如果当前修改的这个值不在选的区间内，那么没有影响，直接计算答案。

具体的，预处理出 f 和 g 分别表示考虑前后缀的最优值，那么答案即为 f_{i-1} + g_{i+1} 。

如果当前修改的值在需要选的区间内，我们可以通过枚举这个区间来算出答案。

直接枚举区间复杂度不能接受，考虑分治优化。

对于分治区间 [L,R] ，我们去考虑当枚举的左端点在 [L,mid] ，枚举的右端点在 [mid+1,R] 时所更新的贡献。

还是斜率优化，在更新 [L,mid] 的答案时加入 [mid+1,R] 的直线，在更新 [mid+1,R] 的答案时加入 [L,mid] 的直线。

这个直接李超树加入和删除线段即可。

总时间复杂度 O(n \log^2 n + q) 可以接受。

Code