本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-11-02 13:34:47

对我来说的难度: A<B<F<D<<C<E

A

从前向后贪心就好了.

B

每个数 $a_i$ 最多被操作 $\lfloor \log_2 a_i \rfloor$ 次.
每次操作,$a_i$ 会变成 $2^{x_i - 1}$ 的倍数.
暴力维护就好了.

C

最优方案是技能 1 干掉一半,剩下使用技能 2 解决.
应最小化使用技能 2 的次数.

考虑最少要用多少次,这里可以显然得出一个结论,设将 $a$ 排序从大到小后,第一个前缀和大于等于 $\frac{\sum\limits_{i=1}^{n}a_i}{2}$ 的元素编号为 $pos$,那么这 pos 个元素都是需要使用技能 $2$ 的.
不难的得出,总答案是 $\lceil \frac{\sum\limits_{i=1}^{n}a_i}{2} \rceil + pos$.

D

显而易见 f 的变化次数是 log 级别,而在 f 相等的情况下, g 的变化次数是 log 级别.
二分就行.

E

贪心题。
可以先拆分成一些由前后互质的数组成的数列。
由于 $1$ 是一个特殊的存在，直接操作非 $1$ 的数，若旁边有相邻的 $1$，那么不会改变与 $1$ 的 gcd，所以将所有 $1$ 找出来，记录所有连续 $1$ 的段落，另外如果连续 $1$ 子段的某一端在 $1$ 或 $n$，则按照贪心策略应放到最后操作。

特别地，如果整个数组全是 $1$，答案是 $n-k$。
具体的，将所有不包含 $1$ 互质子段扔进队列 $1$，所有不包含位置 $1,n$ 的连续 $1$ 子段扔进队列 $3$，另外设一个队列 $2$，后面解释。

然后，很明显，有以下贪心过程。

• 首先遍历队列 $1$，对于非 $1$ 互质段落，可以发现每段从第 $2$ 个开始，到第 $len-1$，隔一个数操作一个数，可以做到每次操作，答案 -2。对于操作剩下的数，如果一个数两边都是 $0$，那么可以扔掉不管，如果仍然剩下两个前后互质的数，将这两个数组成的子段扔进队列 $2$。

• 然后按照长度从小到大遍历队列 3 ，对于连续 $1$ 子段，对于每个子段，若能解决掉 $x \le len-1$ 个数，则答案减去 $x$，否则答案减去 $len+1$。

• 然后遍历队列 $2$，每个区间都有 $1$ 的贡献。

• 最后寻找剩下的 $1$，每个数字 $1$ 有 $1$ 的贡献。

Submission

F

为了方便,将询问离线,提前建立最终的树.

• 操作一,建立新点,应当先消除当前点及其子树原有受到的来自祖先影响.

• 操作二,修改子树,直接改最终形态就行.

对于修改子树,可以提前 dfn 标号,这样整个子树的 dfn 是连续的一段区间,随后使用树状数组.