学校里面写这道题的时候洛谷炸了，自己搞出来了。

Part 0

记当前温度为 TTT ，小于等于 TTT 火战士能量和为 f1(T)f1(T)f1(T) ， 大于等于 TTT 冰战士能量和为 f2(T)f2(T)f2(T) 。

由于能量有剩余的战士会一直战斗下去，此温度下的能量和应该为 min⁡(f1(T),f2(T))\min (f1(T),f2(T))min(f1(T),f2(T)) 。

而对于 f1(T),f2(T)f1(T),f2(T)f1(T),f2(T) 的计算，我们将温度作为下标，即为对于温度 TTT 的前缀和 / 后缀和，考虑使用树状数组。

注意到温度 ≤109\le 10^9≤109 而 Q≤2×106Q \le 2\times 10^6Q≤2×106 ，将温度离散化。

Part 1

我们枚举温度 TTT ，找到能取到能量最大值的最大温度，时间复杂度 O(Q2log⁡Q)O(Q^2 \log Q)O(Q2logQ) 。

Part 2

答案应该为随 TTT 的增大的单峰函数，但是由于最大值可能有很多个，三分法不方便实现。

f1(T),f2(T)f1(T),f2(T)f1(T),f2(T) 应该随着 TTT 的增大而分别单调增和单调减的，为了使两者中最小值最大，答案应该在交点处取到，而考虑到温度的离散，答案不一定能取到交点。

我们可以先二分找出 最后一个 满足 f1(T)

此时时间复杂度 (Qlog⁡2Q)(Q \log ^2 Q)(Qlog2Q) 。

Part 3

类似树状数组找第 kkk 大，由于树状数组中 tree[x]tree[x]tree[x] 管辖的区域是 lowbit(x)lowbit(x)lowbit(x) ，那么从 000 开始，每次加 2i2^i2i ，累计的和一定表示从 111 开始的连续区间。我们根据这一特性在树状数组上倍增找出 k1,k2k1,k2k1,k2 ，这一部分就从原来的 log⁡2Q\log^2Qlog2Q 优化到了 log⁡Q\log QlogQ 。

此时时间复杂度 O(Qlog⁡Q)O(Q \log Q)O(QlogQ) 。