P6619冰火战士是哪个省选联考的题目？

P6619 [省选联考 2020 A/B 卷] 冰火战士 大意 给定一个序列，每个数有两种颜色，要找到一个位置，要找到一个位置使得 \(\min \{ f(p), g(p) \}\) 尽可能大. 思路 我们在温度 \(T\) 下，能参加的冰人必须是 \(y \le T\) 的才能参赛，火人必须是 \(y \ge T\) 才能参赛，我们定义能参赛的冰人的能量和为 \(f(T)\)，同理，火人为 \(g(T)\)。 那么我们的答案一定是 \(2 \times \min \{ f(T), g(T)\}\)，对于这个图，画出来是下面这样的： 那么，取 \(\min\) 之后的图像是这样的： 就是绿色的部分，那么我们这样的话，答案一定在交点附近，那么我们在求这个交点的过程，可以尝试二分 + 树状数组，由于一个是递增，一个是递减，分别维护前缀和和后缀和即可，那么这样二分到交点 \(p\) 的话，只需要看 \(p\) 和 \(p + 1\) 位置，相当于是冰人和火人的位置，火人的位置比较特殊，因为是可能后面还有段连续的区间，需要继续从 \(p + 1\) 向右跳到最后一个合法的区间。 而上述的做法，不难发现时间复杂度是 \(Q \log^2 Q\) 的，无法通过此题，只能有 \(60pts\)，于是我们考虑优化。 有个比较经典的思路（不过我也是刚学会的），在树状数组上倍增，这样的话，我们只需要单 \(\log\) 的复杂度去跳交点，以及查找 \(p + 1\) 的后面最后一个满足情况的点即可。