本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-12-04 01:27:55

考虑将一个完整的区间拆成两段的贡献是什么。

假设 $[l,r]$ 拆为 $[l,mid],[mid+1,r]$。

那么 $[mid,n]$ 所有鱼的价值加 $1$。

注意到，此时本质上是从 $mid+1$ 开始，每个点的编号加了 $1$。

也就是说，问题转化为：$[2,n]$ 共 $n-1$ 个点，对于每个点，都可以选择是否将从这个点开始的所有点的价值加 $1$。

假设一条鱼如果是 Bob 获得，那么是 $1$，反之 $-1$，设 $p_i$ 代表前 $i$ 个鱼的前缀和。

假设第 $i$ 个点选择将其开始的所有点价值加 $1$，那么 Bob 领先 Alice 的分数将会增加 $p_n-p_{i-1}$。

接下来排序贪心就可以。