T1
subtask1: , 暴力枚举每个区间，同时记录区间最大值最小值即可，时间复杂度
subtask2: , 吸口氧，大力出奇迹
subtask3: , 可以各种乱搞
subtask4: , 即询问多少个区间最小值等于最大值，即多少个区间内的所有数都相等，扫一遍统计一下，时间复杂度
subtask5: 正解 表示 有多少个区间满足
那么 最后的答案就是
那么我们可以用双指针的方法去实现，枚举左端点 L, 右端点 R, 那么固定左端点，移动右端点最大值单调不减，最小值单调不增，那么知道扫到右端点 R, 那么 [L, R] 区间内的最大值减去最小值 , 那么此时对应左端点 满足要求的区间个数是 ans+=
然后移动左端点，同时快速维护此时区间的最大值和最小值，用两个单调队列即可， 这个解法时间复杂度
其他类似思想的解法如枚举左端点，二分满足要求的右端点 ， 区间最小值最大值使用ST表维护。也可以在时间复杂度内解决本问题
T2
subtask 1: 这个40分送你的，只需要考虑子序列全是偶数，或者全是奇数即可，显然奇数+偶数 一定等于奇数
值得注意的是：子序列长度至少为3，当 时， 满足要求的子序列是 不是
subtask 2: , 你可以选择爆搜， 时间复杂度
subtask 3 ~ 5: 你可以写一个 的 dp 或者其他乱搞，但是如果你能想到这部分的部分，其实已经离正解不远了。
subtask 6: 因为全部数据 , 那么我们的子序列的模式只能是以下几种：
考虑全偶数注意至少要3个偶数，剩余三种我们可以给出三个pattern 做线性DP即可。
表示前 i 个数中选出子序列 目前已经循环到 pattern[0], 还是 pattern[1] 还是 pattern[2]
转移方程就留给同学们思考了，时间复杂度
T3
subtask 1: , 吸口氧，大力出奇迹，直接暴力模拟， 时间复杂度
subtask 2: 直接找规律， 行不行？
subtask 3: , 首先笔者拿到这道题的第一感觉 和 NOIP 经典问题 《传球游戏》 很像，那么其实最终位置上的数最终的数值是有其他位置上的数 异或起来的，其他位置必须满足到这个位置的传球路径数为奇数， 那么路径数统计，对于 比较小的时候可以构造一个矩阵，跑一下矩阵快速幂，时间复杂度
subtask 4: , 感觉是在提示同学们，没有更好的想法
subtask 5: 正解，我们在 subtask 3 的基础上去考虑，一个数偶数次来到某个位置上等于 这个数就消失了 对后续没有任何影响
那么我们再仔细观察一下，发现传1 次 和 传 2 次， 传 4 次，中间的传递带来的影响最后都消失了
如 传一次
a_i
/ \
a_i a_i
如 传两次
a_i
/ \
/ \ / \
如 如传四次
a_i
/ \
/ \ / \
/ \ /\ / \ / \
你会发现除了 距离为 的位置被 影响了，中间其他的位置都是偶数次影响，即影响最终消失了。
因此我们可以把 拆成 2 的幂次方，每次 , 其中 len 是 T 中拆分出来的 2 的幂次数
最终时间复杂度
T4
subtask 1: 爆搜吧， 笔者没有写，不过应该可以
subtask 2: 因为只有 2个元素，所以序列一定是 1 1 1 1 .... 2 2 2 2 2 2 即前面全是1， 后面全是2 这种形式，所以你手算吧
subtask 3: 同样在 2个元素上 扩展到 3 个元素，一定是 1 1 1 1 1 1 2 2 2 2 3 3 3 3
本质是一个 三元组方案计数问题 , 且 , 三元组计数笔者在安排期末考试时要求写到 求解 原题为： , 且 , 要求写到 感兴趣的同学可以思考一下。
subtask 4 , 6: 这两个task 中 因此只需要做第一问，这里我们分析一下第一问如何快速求解
其答案为组合数 或者 显然两者等价
本问题为从 个有序数中可重复的选出 个数，单调不降的方案数，
举个例子 并且
我们可以构造一个 {2, 3, 4, 5, 6, 7} 共 个数，其中去选择 4 个出来
如果我们选择了 {2, 3, 4, 5}, 那么 第 个位置上的数 减 , 即 {1, 1, 1, 1}
如果我们选择了 {4, 5, 6, 7}, 那么 第 个位置上的数 减 , 即 {3, 3, 3, 3}
所以本题的第一问答案是一个组合数问题
这里你可以使用线性求逆做个递推 也可以 使用费马小定理或者欧拉定理帮助你快速求解组合数取mod
然后我们处理第二问，注意这里的
在第一问的基础上，初始笔者考虑到可以二分逐位确定每一位是多少，这个时间复杂度是够的。后来仔细想想，我们需要放置的是一个单调不降的序列，即放置的数具有单调性，那么我们逐渐尝试放置每一个数，加入我们当前已经放置到了第 位, 如果第 位上放置的数是 , 那么 位上我们还可以放置 数的范围是 $now \sim m, 还可以提供的方案数为：
于是如果 , 那么我们就决定当前位置放 , 并且
由于这部分直接计算方案数不能取mod， 我们可以采用暴力计算组合数的方式，同时验证是否会超过
int C_baoli(int n, int m) {
if (m > n - m) m = n - m;
int ans = 1;
for (int i = 1; i <= m; ++i) {
ans = ans * (n - i + 1) / i;
}
return ans;
}
你也可以提前预处理小于等于的组合数放在vector中，本题就解决了。