A. Sasha and Array Coloring

为了让贡献最大，每种颜色只能染两个数

显然这两个数为最大值与最小值、次大值与次小值、第三大值与第三小值……以此类推即可

B. Long Long

为了让和最大，我们需要的就是把所有负数变成正数

那么第一问的答案就是 \(\sum_{i=1}^n|a_i|\)

此外，因为每次变号操作都是针对区间的，所以我们考虑优化操作次数：每次操作都是针对 极长负数子串

第二问的答案就是极长负数子串的数量

大水题，比 A 和 B 还简单

直接从结点 \(n\) 开始往上跳即可，显然每跳一次都会 \(n\leftarrow\lfloor\frac{n}{2}\rfloor\)

组合数学水题，根据乘法原理，用 DFS 统计以 \(x\) 为根的子树的叶子结点数量，记为 \(siz_x\)，每次询问输出 \(siz_x\times siz_y\) 即可

二分答案

check 的时候，把当前所有的单点修改存起来，然后依次遍历每个区间，观察这个区间内被单点修改的点的个数是否严格大于该区间长度的一半即可

接下来只要套一个单点修改区间查询即可

（待补）