A：

签到题，根号分治，对于小于 $\sqrt n$ 的 $y$ 预处理后缀和，其他的暴力跳即可。

B：

对于一个区间，我们想让它最大只需要保证选择的区间都包含它即可。

考虑将所有区间下放到线段树上，然后遍历整棵树，遍历到一个节点时对当前节点存的区间做背包，若子树中没有下放区间的节点，用 dp 数组更新 vis 数组，否则遍历子树，离开节点时将对 dp 的更新撤销。

C：

先离线。

你考虑维护一个长得像历史和的 DS，你维护一个指针 $r$ 扫一遍整个序列，线段树上每个叶子 $l$ 代表 $[l,r]$，这段子区间的前缀中有多少个含有奇数个不同的数。

对于不同的数我们有经典 trick 你记一个 $pre_i$ 表示与 $a_{pre_i}=a_i$ 且离 $i$ 最近的数，那你每次要更改的就是 $[pre_r+1,r]$ 这段区间的奇偶性。

然后你对 $[1,r]$ 这段前缀所有为奇数的点进行一个整体加一，你考虑这个玩意咋维护。

一个比较 navie 的想法是上矩阵，常熟太大，我们有全♂新♂做♂法♂。

考虑维护两棵线段树，然后每次反转奇偶性就是交换对应区间，然后整体加一只对一棵线段树做就行了。

D：

先合并连续段，将值取 max，计合并完的段数量为 $cnt$，那么最多能取到的点的个数为 $\lfloor \frac{cnt-1}{2} \rfloor$。

一个结论是 $[2,cnt-1]$ 内的点任选 $\lfloor \frac{cnt-1}{2}\rfloor$ 个点都是可以取到的，考虑你每次取完点后还要从相邻的点中再消掉一个，而剩余点的数量显然大于选择的点的数量，所以一定有合法方案。

排个序，取前 $\lfloor \frac{cnt-1}{2} \rfloor$ 个点就完了。