「JOI Open 2019」三段跳び

题意：

\(n\) 个数，\(q\) 次查询，每次给出区间 \([l,r]\)，求区间内满足以下条件的三元组 \((x,y,z)\) 中 \(a_{x}+a_{y}+a_{z}\) 的最大值：

• \(x<y<z\)。

• \(y-x\le z-y\)。

做法

考虑可能成为答案的 \(x\) 和 \(y\) 组成的二元组 \((x,y)\) 是很少的。事实上，这是 \(\mathcal O(n)\) 级别的。我们可以考虑这样的 \((x,y)\) 满足的性质：其必然有 \(\max\limits_{i=x+1}^{y-1}a_i\le\min\{a_x,a_y\}\)，否则将一个小的位置换成中间的最大值肯定更优。

而这个条件非常舒服，可以直接单调栈求出这些二元组。具体地，维护一个不降的栈，在访问栈顶时（不一定要成功弹栈）把顶端元素与当前元素组成的二元组加入。这样容易发现不会漏掉任何一个合法的二元组。

得到这 \(\mathcal O(n)\) 个二元组过后怎么快速计算呢？考虑离线下来，按左端点排序，扫描线从右往左扫，不断加入新的二元组，并对某一个后缀进行更新，表示这一个后缀作为 \(z\) 可以与 \((x,y)\) 组合。具体地，令 \(b_i\) 为 \(i\) 作为 \(z\) 时 \(a_x+a_y\) 的最大值。那么修改操作就是区间的 \(b_i\) 对一个值取最大值，查询的是区间 \(a_i+b_i\) 的最大值。这个用线段树怎么做呢？

答案很简单！维护某个区间的 \(a_{\max}\) 和 \(v_{\max}\) 表示区间内 \(a_i\) 的最大值与 \(a_i+b_i\) 的最大值，那么当更新的值为 \(d\) 时只需要 \(v_{\max}\leftarrow \max\{v_{\max},a_{\max}+d\}\) 即可。自己稍加思考便可想清楚了。

至此，我们用 \(\mathcal O((n+q)\log n)\) 的时间复杂度解决了这个问题。