本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目标题 难度 T1 大大和1 入门 T2 午枫的博弈 普及- T3 小午的请求 普及- T4 小枫爬山 普及/提高- T5 午枫的双人挑战 普及/提高- T6 大大和2 普及+/提高
T1 大大和1
题目大意
有一个长度为 nnn 的数组 aaa ，判断是否存在一个区间 [i,j][i,j][i,j] 满足 max(ai,ai+1,…,aj−1,aj)≥ai+ai+1+⋯+aj−1+ajmax(a_i,a_{i+1},\dots,a_{j-1},a_j)\geq a_i+a_{i+1}+\dots +a_{j-1}+a_jmax(ai ,ai+1 ,…,aj−1 ,aj )≥ai +ai+1 +⋯+aj−1 +aj 。
解题思路
当 i=ji=ji=j 时，一定满足 ai=aia_i=a_iai =ai 。所以答案一定是 YES
参考代码
T2 午枫的博弈
题目大意
有 nnn 个数，小午只能隐藏奇数位置的数，小枫只能隐藏偶数位置的数，两人轮流行动，小午先手，若最后剩下一个数时结束，剩下的数如果是奇数，小午获胜，否则小枫获胜。求最终谁一定会赢。
解题思路
因为每个人可以选择隐藏的数和对方没有交集，所以在隐藏数时，小午会优先选择隐藏偶数，小枫会优先先择隐藏奇数。
当 nnn 为奇数时，判断奇数位置是否有奇数，有则输出 Noon ，否则输出 Maple ； nnn 为偶数时，判断偶数位置是否有偶数，有则输出 Maple ；否则输出 Noon。
参考代码
T3 小午的请求
题目大意
有 nnn 个数字，从中选出一些数，使得选出的数之和为偶数且最大，求这些数字之和。
解题思路
考虑要选出和最大的数，因为没有负数，所以我们可以直接把所有数都选了，如果和为偶数，那这就是最大的数字和了；否则说明其中至少有一个奇数，把最小奇数剔除就可以得到最大的数字和。
参考代码
T4 小枫爬山
题目大意
有 nnn 级台阶，mmm 位爬山者，每位爬山者腿长 bib_ibi ，如果下一级台阶与爬山者所在台阶的高度差大于爬山者的腿长，就无法继续往上爬了。求每位爬山者能爬到的最大高度。
解题思路
对于每一次询问，我们可以对每级台阶的高度差进行二分查找，找到第一个大于 bbb 的台阶，这级台阶的前一级就是最终到达的位置。但是二分需要有单调性，我们可以用 viv_ivi 记录前 iii 个位置最大的高度差，对 vvv 二分即可。
对于每一个台阶实际的高度，我们可以用前缀和快速求出。
参考代码
T5 午枫的双人挑战
题目大意
一共有 nnn 个关卡，每个关卡分为解密和战斗两部分，挑战关卡有两个限制：
* 对于不同关卡，只有完成了前一关的解密部分才能进行下一关的解密部分；
* 对于同一关卡，只有完成了这一关卡的解密部分才能进行这一关的战斗部分。
第 iii 关的解密部分需要耗时 aia_iai ，战斗部分需要耗时 bib_ibi ，完成了一关的揭秘和战斗部分才视为完成这一关。对于 qqq 个询问，求完成 kkk 个关卡的最短用时。
解题思路
首先考虑完成 kkk 个关卡，我们需要至少完成前 kkk 个解密部分 ，完成 bib_ibi 之前我们需要至少完成前 iii 个解密部分。
接下来我们需要考虑的是选择完成哪几个关卡所花的时间最少。由于询问次数只有 100100100 ，所以对于每一个询问可以尝试使用 O(n)O(n)O(n) 甚至 O(nlogn)O(nlogn)O(nlogn) 的复杂度去完成。由于完成解密部分一定是连续的，所以我们可以先用前缀和 sis_isi 求出前 iii 个解密部分所花时间是多少。
我们可以枚举最后一个被完成的关卡的哪个，此时的时间花费是 si+bis_i+b_isi +bi ，其余的 k−1k-1k−1 个战斗部分选择 bib_ibi 最小的 k−1k-1k−1 个，但是这样的做法时间复杂度会来到 O(n2)O(n^2)O(n2) ，显然是不合理的。其实我们可以通过优先队列优化选 bib_ibi 的过程，我们先选出前 kkk 关卡完成，将 bib_ibi 都存入优先队列中，往后枚举时，设当前枚举的位置为 jjj ，如果 bjb_jbj 小于优先队列中最大的元素，则可以把 bjb_jbj 与优先队列中最大元素替换。每次算出所需要的时间，更新答案。这样查询的时间复杂度为
O(nlogn)O(nlogn)O(nlogn) 。
总时间复杂度为 O(n+knlogn)O(n+knlogn)O(n+knlogn) 。
参考代码
T6 大大和2
题目大意
有一个长度为 nnn 的数组 aaa ，判断是否所有区间 [i,j][i,j][i,j] 满足 max(ai,ai+1,…,aj−1,aj)≥ai+ai+1+⋯+aj−1+ajmax(a_i,a_{i+1},\dots,a_{j-1},a_j)\geq a_i+a_{i+1}+\dots +a_{j-1}+a_jmax(ai ,ai+1 ,…,aj−1 ,aj )≥ai +ai+1 +⋯+aj−1 +aj 。
解题思路
我们考虑对于每一个位置 iii ，如果这个位置的数是区间最大值，首先找出所有满足这个数为最大值的区间，这部分我们可以用单调栈求出左边和右边第一个大于这个数的位置 LiL_iLi 和 RiR_iRi ，时间复杂度是 O(n)O(n)O(n) 线性的。
然后对于每一个位置 iii ，在区间 [Li,Ri][L_i,R_i][Li ,Ri ] 中，如果最大的区间和比这个数还要小的话，那么这个位置就是满足条件的。在找最大区间和时，需要注意，由于位置 iii 一定需要在区间中，所以我们需要在 [i,Ri−1][i,R_i-1][i,Ri −1] 中找到最大前缀和 mxsmxsmxs ，在 [Li,i−1][L_i,i-1][Li ,i−1] 中找到最小前缀和 mismismis ，区间 [Li,Ri][L_i,R_i][Li ,Ri ] 中的最大区间和就是 mxs−mismxs-mismxs−mis 。
可以用 ststst 表或者线段树快速查询区间最大最小前缀和。
时间复杂度 O(nlogn)O(nlogn)O(nlogn) 。
参考代码
