题解：P14462 【MX-S10-T3】『FeOI-4』寻宝游戏
首先考虑一次查询怎么做。
考虑以下策略：
- 选择一个位置作为基准，将所有的泡面移到这里。
令最大的位置为
mx ，严格次大的位置为se （即a_{se}<a_{mx} ）。容易发现基准一定是
se 或mx （因为奇偶性可能不对）。两个都试一下即可。特别地，当所有
a_i=1 时，有可能使用n+1 作为基准。
- 将所有泡面移入位置
k 。令剩下最多有
x ，剩余的和为S 。若奇偶性不对需要先从基准和x 中拿出一个放入n+1 。
- 若
x\le S ，直接全移过去即可。具体来说，每次选择最多的两个位置，各拿出一个放入k 。操作次数为(x+S)/2 。- 若
x> S ，可以这样：从S 中和x 中拿出一个，放入n+1 ，直到合法。操作次数为x 。发现操作次数为
\max((S+x)/2,x) 。容易发现这个策略在
n\ge 3 时是对的。考虑特判
n=1,n=2 的情况。考虑
n=2 的情况。令他们为x,y(x\le y) 。
当
x,y 比较大的时候，答案为x 。当
y 比较大的时候，答案只与x 有关。剩下的情况可以 打表/手玩 求出来。
具体来说，我们只需要玩出
x,y\le 6 和x\le 6,y> 6 的情况即可。
通过上述贪心方法，可知只有区间和，区间最大值，区间次大值，区间严格次大值对答案有影响。
使用数据结构简单维护即可。
时间复杂度