A

• 的情况，答案是 。
• 的情况，我们把每两次按钮先捆绑在一起，算出 。
  • 然后判断是否可以在前 次就完成任务，即判断 。
  • 如果上式成立，答案是 ，否则是 。

B

提供一个比较暴力的做法。对于至少有两位的数字，它是 的倍数，等价于最后两位组成的数是 的倍数。

记录出现的所有数位（以及次数），然后枚举 。

• 如果 ，那么可以输出 YES 的条件是 是 的倍数，且数位 都有在原数出现。
• 如果 ，那么可以输出 YES 的条件是 是 的倍数，且数位 在原数出现至少两次。

注意特判一位数的情况。

C

由第一个式子：异或和不是 ，那么它一定大于 。

将这个不等式代入第二个式子，那么必有：。

而最小公倍数一定是序列每个数（包括最小数）的倍数，因此 。

所以，要求 每个数相等。

然后别忘了异或和不是 ，结合上一行的结论可知我们只能选奇数个相等的数。

所以如果某个数在序列出现奇数次可以一次删空；如果出现偶数次就需要删除两次（偶数 = 1+奇数）。

D

为了让 尽量大，我们应该让所有不为 的 值都不一样。

同时我们想要所有数的和尽量小，根据贪心策略，对于越大的 ，对应的 应该越小。

例如，我们想要让 等于 ，构造的总和最小的序列是 ，这样 。

因此，当 等于 时， 的下限应该是 。

化简后是 。

对于每个询问，可以二分出最大的一个不超过 的 ，输出 即可。注意二分过程不要溢出了。

P.S. 由于这个数这是 级别的，也可以暴力求出所有在 以内的 。

E

对于一个节点 ，它的颜色会波及到 与 的链上所有点的贡献。

假设 初始的子树内红点有 个，蓝点有 个。假设节点 在 节点的子树内。

• 若 由红变蓝，且 ，那么 会减少 。
• 若 由红变蓝，且 ，那么 会增加 。
• 若 由蓝变红，不等式左边改成 即可判断。

因此我们 DFS 两次。

• 第一次统计每个节点所在子树的红蓝点个数。
• 第二次对于每个 ，树上前缀和求出 到 的链上每个点 中，满足 ，；， 的点数。根据节点 颜色的变化情况得到 的变化量，再根据变化量的正负统计答案数。

F

利用若干个 vector 分别记录每个值的出现位置集合。我们先把原序列每个数取出，然后按照数值从大到小的顺序把数字放回。

放回的过程中，假设当前考虑等于 的数（先不放回），那么所有满足 的区间 ，里面放回的数都大于 。

所以每个区间的贡献，等于放回区间内的数的个数。求完贡献后把所有等于 的数放回。

以上操作可以用树状数组快速维护、查询。

区间数太多了怎么办？ 怎么乘上去？我们可以只先关注极小有效区间，即满足 但中间不存在等于 的数的区间 。

区间长度为奇数，等价于左右端点的奇偶性相同；区间长度为偶数，等价于端点的奇偶性相反。

所以对于极小区间 ，假设四个量，这都可以用线性复杂度求出：

• 中等于 且下标是奇数的元素个数 ；
• 中等于 且下标是奇数的元素个数 ；
• 中等于 且下标是偶数的元素个数 ；
• 中等于 且下标是偶数的元素个数 。

那么区间 对整个序列的贡献是 。

这个贡献可以代表所有包含 且端点等于 的区间，在 这一段产生的贡献和。

容易证明极小有效区间数是 的，所以总时间复杂度是 。