挑战赛#22全题解
希望AC君能选中我的题解，感谢万分。
前言
赛时 T6 过了，但不是正解，看看就好。
感觉这次题挺简单的（除了T5)
T1(大大和1)
对于每个数对 (i,j)(i, j)(i,j)，可以发现，当 i=ji = ji=j 的时候必然满足题目中所提到的条件：
max(ai ,ai+1 ,…,aj−1 ,aj )≥ai +ai+1 +⋯+aj−1 +aj max(a _ i ,a _ i+1 ,…,a _ j−1 ,a _ j )≥a _ i +a _ i+1 +⋯+a _ j−1 +a _ j max(ai ,ai +1 ,…,aj −1 ,aj )≥ai +ai +1 +⋯+aj −1 +aj
所以对于每组数据，我们的输出都应当是 YES。
T1代码部分
T2(午枫的博弈)
乍一看题目很难，其实仔细观察题目可以发现，因为这俩人都是绝对聪明的，也就是说他们采取的是最优策略，也就是贪心，因此我们可以找出规律（请看代码部分）。
T2代码部分
T3(小午的请求)
看见题目第一眼让我想起了dp。
写这道题我们需要用到一个非常重要的性质：奇数减去奇数等于奇数。
因为题目要求让我们选出最大和为偶数的，那么整个序列和无非就两种情况：奇数或者偶数
如果是偶数，那肯定最好了，不用加也不用减，就是最大值。
否则的话，如果是奇数，那么我们就减去序列中最小的那个奇数，就是这道题的答案了。
T3代码部分
T4(小枫爬山)
这道题直接模拟是会超时的，因为 (1≤n,m≤5×105)(1≤n,m≤5×10^5)(1≤n,m≤5×105)，O(n2)O(n^2)O(n2) 一定过不了。
因为题目保证 hi ≤hi+1h_i ≤h_i+1hi ≤hi +1 而且需要查找第 iii 个爬山者最高能爬到的高度。
这很容易就能想到用二分查找来写。
但是需要注意的是，第 iii 个楼梯的长度需要的腿长不一定是 hih_ihi ，因为这些山呈楼梯状，所以 第 iii 个楼梯的长度需要的腿长是 hi−hi−1h_i-h_{i-1}hi −hi−1 ，我们查找就应该查找一个已经维护好了的数组里面的数（详情请看代码部分）。
T4代码部分
T5(午枫的双人挑战)
应该是本场最难。
通过遍历所有可能的终点关卡 MMM，计算完成前 MMM 关解密的总时间加上从 1 到 MMM 关中选取最小的 kkk 个战斗时间的总和。使用大根堆维护当前最小的 kkk 个战斗值，确保每次都能高效更新最优解。最终取所有 MMM 情况中的最小值作为完成 kkk 个关卡的最短时间。(更详细的请看代码部分)。
T5代码部分
T6(大大和2)
倒不如T5来当T6合适
说实话我赛时过的真的很迷（应该是数据太水了）。
这道题与 T1 有所不同的是，T1只要求要一对满足即可，这道题需要满足所有对数才是 YES。
很显然，只需要检查连续长度为 2 和 3 的子数组即可（正确性还证明不出来）。
当 n≤5000n ≤ 5000n≤5000 时，模拟是肯定能过的，所以为了稳妥，我采取用模拟来写。
否则则用检查连续长度为 2 和 3 的子数组的方法来写。
T6代码部分
希望这几篇题解对你赛后补题能起到作用。
