抉择

考虑 dp，$dp(i)$ 表示，考虑前 $i$ 个数，$a_i$ 选了，的最大权值，转移枚举 $j(j \gt i)$。

优化转移，如果 $i,j$ 之间有一个 $k(i \lt k \lt j)$，且 $a_i \&a_k$ 的最高位和 $a_i \& a_j$ 相同，那么选上 $a_k$ 一定更优（$2 \cdot 2^{a_i \& a_j 的最高位} \gt a_i \& a_j$，枚举 $a_i \& a_j$ 的最高位，找到前面第一个这一位是 $1$ 的数转移就行，复杂度 $O(n \log A)$。

赛时有人挂，原因是没考虑 $a_i \& a_j=0$ 的情况，hack：$a=\{4,4,2,2\}$。

fun fact: pb 认为这个题是一眼题。

重生

最直观的一个结论：除了最后一条命，都只做”深入思考“操作。

考虑二分，二分复活次数 $d$，计算经过 $d$ 条命的“深入思考”后，最少在下一条命中需要多少时间能完成任务。最后一条命，每个任务需要的时间是：

• $t=0$，需要时间为 $0$。
• $t \le d$，需要时间为 $1$。
• $t \gt d$，需要时间为 $t-d+1$。

考虑这样一个贪心策略，每次选择能减少时间最多的进行“深入思考”，原因是代价关于 $t$ 是凸的。

假设任务 $i$ 被想了 $t$ 次，则需要满足：$t \le d, \sum t \le c \cdot d$。

但是 $c,d$ 可能会特别大，观察到对于 $t \ge 2d$ 的任务，进行一次“深入思考”会产生 $d$ 的时间减少。将所有任务按 $d$ 从大到小排序，尽可能操作直到 $t \lt 2d$ 或操作次数用完。之后每个任务至多被操作两次，把这两次的时间减少量搞出来再贪一遍就行。

复杂度 $O(n \log n \log A)$。

fun fact: 我认为这个题是一眼题。

遍历

考虑点双缩树，$x$ 走到 $z$ 必须经过 $y$，当且仅当 $y$ 是割点，且 $x$ 和 $z$ 在 $y$ 的不同子树中。

分 $y$ 是否在 $x$ 子树两种情况讨论，每种情况都分别令 $O(1)$ 个 dfs 序区间内的点不合法。

复杂度 $O(n \log n)$，有一种情况需要求 $x$ 的 $dep_y-dep_x-1$ 级祖先，

fun fact：这个题成为了签到题，前三题通过 $18,12,22$ 位选手。

排序

讲下我的做法，实测 $118$ 次操作，能过原题。

考虑只有 $0,1$，将连续段放在一起考虑，序列形如 $10101010 \cdots$，考虑一次操作让 $0$ 连续段个数减半，分段类似 $1|0|10|1|0|10\cdots$，最后可能会搞出 $101$ 的形式，再来一次操作 $1|01$，就能排好序了。

考虑分治，将 $\le n/2$ 的看成 $0$，$\gt n/2$ 的看成 $1$，进行只有 $0,1$ 的算法，然后往两边递归，同一层可以放在一起处理，如果最后顺序不对再整体 reverse 一下就行。操作次数大概是 $0.5 \cdot\log^2 n$