题解：AT_abc467_f [ABC467F] Email Scheduling Optimization

· · 题解

假设已经安排好了做任务的顺序，那么所需要的时间为所有任务结束时间的最大值，即

\max_{i=1}^n(\sum_{j=1}^i a_j+b_i)

没有修改操作的话是一个经典的贪心：以 b_i 为关键字从大往小做这些任务最优。

因此可以将 b_i 离散化后翻转当作下标，从前往后扫描统计答案。

但每次修改之后就要重新扫一遍，考虑优化。

记 f(l,r)=\max_{i=l}^r(\sum_{j=l}^i a_i+b_i)，答案即为 f(1,n)。

而对于 k\in [l,r)，有：

f(l,r)=\max_{i=l}^r(\sum_{j=l}^i a_j+b_i)\\ =\max(\max_{i=l}^k(\sum_{j=l}^i a_j+b_i),\max_{i=k+1}^r(\sum_{j=l}^i a_j+b_i))\\ =\max(\max_{i=l}^k(\sum_{j=l}^i a_j+b_i),\sum_{j=l}^k a_j+\max_{i=k+1}^r(\sum_{j=k+1}^i a_j+b_i))\\ =\max(f(l,k),f(k+1,r)+\sum_{j=l}^k a_j)

说明区间的答案可以合并，可以用线段树维护区间 [l,r] 的 f(l,r) 和 \sum_{i=l}^r a_i。时间复杂度 \mathcal O(n\log n)。

代码写的有点抽象。