A

简单题，大胆猜结论，答案为不同的数字个数乘二减一。

但是赛时离散化忘记指定特值。

证明

把目标数组去重后降序排列，令其为数组 \(a\)，长度为 \(m\)，对于 \(i = 1,2,\dots,m-1\)，执行以下操作：

  1. 增加 \(a_i - a_{i+1}\)。
  2. 对于所有 \(a_j \neq a_i \text{且} j > i\)，清空。

最后增加 \(a_m\)。

B

简单题，博弈论。

最优情况一定是 Krug 被逼到了边缘，所以 Doran 也要走到边缘。

根据 Krug 和 Doran 的相对位置取 MAX 即可。

C

难度不大。

考虑一个数列如果不全是 \(0/1\) 交替的，那么每次操作一定会有两个相邻的 \(0/1\)。

如果全是 \(0/1\) 交替的，只存在一次操作没有相邻的 \(0/1\)，即答案会多 \(1\)。

前缀和预处理即可。

D

赛时卡题了，观察结论题。

首先不看增加的操作，将一个数清到 \(1\) 需要 \(\log_2 a_i\) 次。

对一个偶数加 \(1\) 没有用，立马除就可以。

如果一个数在不断除 \(2\) 的时候，出现了不为 \(1\) 的奇数，然后对这个数执行 \(+1\)，那么怎么除都不行，所以贡献会多 \(1\)。

所以除了 \(2\) 的幂外，其它数贡献都会多 \(1\)。

但是，还有一类特例，对于 \(2^k + 1~(k\in \mathbb{Z}^+)\)，如果先除贡献就不会多，先加贡献就会多 \(1\)，先手最多除一半的数，所以贡献会多一半。

E

赛时没做出来，构造题还是做少了。

看到构造想到询问特例，于是先询问所有点。

然后每次询问除了已经回答过的点。

如果某次回答长度大于等于 \(n+1\)，直接输出。

否则，从每次询问向前面询问的点连边，跑 DAG 上 DP 即可。

F

思考题。

转换条件，满足 \(\max\{x,y,z\} - \min\{x,y,z\} > z\)，贪心的想，相当于满足 \(a_{i+2} - a_i > z\)。

所以我们可以选区间开头的两个点，\(l\) 和 \(l+1\)，两个点不断向后跳满足条件的点。

我们就看成后面的点向前面的点连边，树上倍增优化即可。

但是两个点可能会调到重复的点，即两点的 \(lca\)，此时显然要从 \(lca\) 和 \(lca+1\) 重新开始跳。

于是再维护另一个倍增，表示跳到重复的点。

查询时先跳第二个倍增，如果区间还有剩余再跳第一个。