ARC 180 D - Division into 3
首先考虑分成两段，首先两端中必定有一个是最大值，问题就是让另一段的最大值最小化。
并且这两段一定一个是前缀 \(\max\)，一个是后缀 \(\max\)，那么显然就是只留第一个值或者只留最后一个值。所以就是 \(mx+\min(a_l,a_r)\)，然后考虑分成三段。
对于一组询问 \([l,f]\)，我们可以通过线段树求出 \(mx\) 的位置 \(p\)，有以下两种情况：
- \(p\) 在中间段：答案是 \(mx+a_l+a_r\)\
- \(p\) 在第一段（第三段同理）：就是后缀区间中 \(mx + \min(a_l,a_r)\) 的 \(\min\)。
对于第二种情况我们将问题转换为了：
给你一个序列，每次给你一个区间 \([l,r]\)，需要求出一下式子最小值：
满足 \((l\le i<r)\)。
然后发现最小值取到的 \(i\) 要么是 \(r-1\)，否则一定满足 \(a_i < a_r\)。
证明：
因为 \(mx_{[i,r]}\) 是随着 \(i\) 的减小而增大的，只有让第二项变小才能比 \(i=r-1\) 时更优。
于是我们直接默认 \(a_i<a_r\) 即可，因为如果是 \(a_i\ge a_r\) 显然更劣。
也就是需要求出一下式子的最小值：
然后我们考虑扫描线：
发现不太好做，但是我们有一个骚操作，用一个单调栈（递增），每一次插入 \(i\) 我们会弹出一些元素，每次弹出就对应的在线段树上撤销，然后加上目前插入的 \(i\) 值的贡献。那么这一题就做完了，需要线段树支持区间加，区间 \(\min\)，以及区间 \(\max\) 的位置。
总结：如果以后遇到区间查询区间的式子中含有后缀/前缀的最大值最小，或者最小值最大，且式子较为复杂，可以用扫描线+单调栈。