题目 做法难度 T1 可以，枫总司令 入门\red{入门}入门 T2 巴仈博弈 普及−\orange{普及-}普及− T3 欢乐赛T6 普及−\orange{普及-}普及− T4 爬山 普及−\orange{普及-}普及− T5 看着简单做着难 普及+/提高\green{普及+/提高}普及+/提高 T6 保证思维量与使用数据结构难度成反比 普及+/提高\green{普及+/提高}普及+/提高（提高+/省选−\blue{提高+/省选-}提高+/省选−）
T1
可以，枫总司令。
注意到 i=ji=ji=j 时，maxk=ijAk=Ai=∑k=ijAk\max_{k=i}^j A_k=A_i=\sum_{k=i}^j A_kmaxk=ij Ak =Ai =∑k=ij Ak ，所以对于任意数组，一定存在符合要求的数对，直接输出 YES 即可。
时间复杂度：O(t)O(t)O(t)？不到啊。
T2
典型的无脑博弈。
注意到如果 nnn 为奇数，则偶数下标的数都会被隐藏，奇数下标剩一个；否则奇数下标的数被隐藏，偶数下标的数剩一个。
所以只要 nnn 为奇数时，小午选一个奇数不隐藏，当 nnn 为偶数时，小枫选一个偶数不隐藏即可必胜。关键就在于他们有没有。
时间复杂度：O(n)O(n)O(n)。
T3
本题做法有很多，这里贴一个最无脑的 DP 做法。
dp[i][0]dp[i][0]dp[i][0] 表示前 iii 个数选择的结果为偶数的最大值，dp[i][1]dp[i][1]dp[i][1] 表示奇数的最大值。则：
* 当 AiA_iAi 为奇数时，dp[i][0]=max{dp[i−1][0],dp[i−1][1]+Ai}dp[i][0]=\max\{dp[i-1][0],dp[i-1][1]+A_i\}dp[i][0]=max{dp[i−1][0],dp[i−1][1]+Ai }，dp[i][1]=max{dp[i−1][1],dp[i−1][0]+Ai}dp[i][1]=\max\{dp[i-1][1],dp[i-1][0]+A_i\}dp[i][1]=max{dp[i−1][1],dp[i−1][0]+Ai }。
* 当 AiA_iAi 为偶数时，dp[i][0]=dp[i−1][0]+Ai,dp[i][1]=dp[i−1][1]+Aidp[i][0]=dp[i-1][0]+A_i,dp[i][1]=dp[i-1][1]+A_idp[i][0]=dp[i−1][0]+Ai ,dp[i][1]=dp[i−1][1]+Ai 。
注意不存在不选数结果为奇数的情况，所以应把 dp[0][1]dp[0][1]dp[0][1] 设置成 −∞-\infty−∞。
时间复杂度：O(n)O(n)O(n)。
T4
这么一眼的吗，滚去 T2。
很显然，差分+前缀最大值+二分即可。
时间复杂度：O(mlogn)O(m\log n)O(mlogn)。
T5
怎么突然开始上难度了。
拼尽全力无法想出 O(qn)O(qn)O(qn) 解法，只能写一个 O(qnlogn)O(qn\log n)O(qnlogn) 卡常过了。
考虑单次询问怎么做。
注意到如果完成前 iii 个解密，那肯定选前 iii 个挑战中前 kkk 小的时间。加上 AiA_iAi 前缀和求最小值即可。显然可以用大根堆 O(nlogk)O(n\log k)O(nlogk) 解决。
但是堆的常数有亿点大，100×(2×105)×⌈log2(2×105)⌉=3.6×108100\times (2\times 10^5)\times \lceil\log_2(2\times 10^5)\rceil=3.6\times 10^8100×(2×105)×⌈log2 (2×105)⌉=3.6×108，稍微带点常数就寄了。看来我们需要使用一个常数更小的数据结构。
有什么数据结构可以常数小、能 O(logn)O(\log n)O(logn) 求出前 iii 个元素的前 kkk 小的元素呢？很显然，树状数组神力！
我们离散化一下，确定每个 BiB_iBi 对应的位置 CiC_iCi ，使得 CiC_iCi 各不相同且对于 i,ji,ji,j，当 Bi<BjB_i\lt B_jBi <Bj 时 Ci<CjC_i\lt C_jCi <Cj ；
开两个树状数组 t1,t2t_1,t_2t1 ,t2 ，在更新第 iii 个数时，将 t1[Ci]t_1[C_i]t1 [Ci ] 的值 +1+1+1，t2[Ci]t_2[C_i]t2 [Ci ] 的值 +Bi+B_i+Bi ；查询时直接树状数组二分，找到第一个（最后一个也行）iii 使得 (∑j=1it1[j])≥k(\sum_{j=1}^i t_1[j])\ge k(∑j=1i t1 [j])≥k，然后查询 ∑j=1it2[j]\sum_{j=1}^i t_2[j]∑j=1i t2 [j] 即可。
离散化、修改树状数组的时间复杂度为 O(nlogn)O(n\log n)O(nlogn)，常数很大，但不影响；而查询的时间复杂度为 O(qnlogn)O(qn\log n)O(qnlogn)，常数约为 111。这样就可以在规定时间内通过该题。
时间复杂度：O(qnlogn)O(qn\log n)O(qnlogn)，常数特小可以通过。
T6
将式子转换一下：
maxk=ijAk≥∑k=ijAk ∑k=ijAk≤maxk=ijAk ∑k=ijAk−maxk=ijAk≤0\max_{k=i}^j A_k\ge\sum_{k=i}^j A_k\\\space\\ \sum_{k=i}^j A_k\le\max_{k=i}^j A_k\\\space\\ \sum_{k=i}^j A_k-\max_{k=i}^j A_k\le 0 k=imaxj Ak ≥k=i∑j Ak k=i∑j Ak ≤k=imaxj Ak k=i∑j Ak −k=imaxj Ak ≤0
所以我们只需要对于每个 iii，判断 maxj=1i(∑k=jiAk−maxk=jiAk)≥0\max_{j=1}^i(\sum_{k=j}^i A_k-\max_{k=j}^i A_k)\ge 0maxj=1i (∑k=ji Ak −maxk=ji Ak )≥0 即可。注意，iii 是连续的，所以可以根据前面的结果推出后面的结果。
先看和的部分。
很简单，开一颗线段树，更新 AiA_iAi 时在 [1,i][1,i][1,i] 加上 AiA_iAi 即可。
然后就要思考如何求最大值了。
假设原来的区间最值为 [9,9,6,4,4,4,3,2,2,0,0][9,9,6,4,4,4,3,2,2,0,0][9,9,6,4,4,4,3,2,2,0,0]（000 是给第 10,1110,1110,11 个元素占位用的），现在添加了第 101010 个元素 555，那么就需要将区间最值变为 [9,9,6,5,5,5,5,5,5,5,0][9,9,6,5,5,5,5,5,5,5,0][9,9,6,5,5,5,5,5,5,5,0]，则你需要：
* 将区间 [4,6][4,6][4,6] 的值加 111。
* 将区间 [7,7][7,7][7,7] 的值加 222。
* 将区间 [8,9][8,9][8,9] 的值加 333。
而这时再添加第 111111 个元素 777 呢？区间最值就变为了 [9,9,7,7,7,7,7,7,7,7,7][9,9,7,7,7,7,7,7,7,7,7][9,9,7,7,7,7,7,7,7,7,7]，你只需要将区间 [3,3][3,3][3,3] 的值加 111，[4,11][4,11][4,11] 的值加 222 即可。
注意到这个操作完全可以用单调栈实现。弹出时更新线段树即可。
显然，单调栈最多只能弹出 O(n)O(n)O(n) 次，所以整体时间复杂度还是 O(nlogn)O(n\log n)O(nlogn) 的。
时间复杂度：O(∑nlogn)O(\sum n\log n)O(∑nlogn)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
赛后发现我 T5 优化了个寂寞。甚至有人大根堆解法比我还快。
