P10675 【MX-S1-T4】先见之明

MiniLong · 2025-09-03 15:35:06 · 题解

对于一次询问，考虑有哪些可能的解。首先是一些特殊的答案：ans=k,2^{p_1 + 1},2^{pre_{p_1 + 1}}，其中 pre_i 为 最小的 a_j 使得 a_j \ge i，这些都是可以快速判断的，先不考虑。

再就是答案肯定是 k 的一段前缀 +2^j，其中 j\notin k。设答案取了 2^{p_1} \sim 2^{p_i} 和 2^j (p_i > j > p_{i+1})，考虑这个 j 的取值可能是哪些。

• 如果这个 2^j 是用一些 \le 2^{p_{i+1}} 的 a 凑成的，那么肯定经过了这些 a 先加到 2^{p_{i+1}+1} 再不断进位到 2^j，既然中间都存在到一个更小值的过程，那把 j 换成 p_{i+1} + 1 肯定更优，所以一种可能的取值是 2^{p_{i+1} + 1}。

• 如果 2^j 用了 > 2^{p_{i+1}} 的 a 凑，那么这些 a 肯定不会 \le 2^{p_{i+1}}，理由同上。那么肯定只用一个 a 最优，且这个 a 肯定是出现在 [p_{i+1} + 1,p_{i} - 1] 中最小的那个，证明和上面类似：如果取的不是最小那个，那么这个最小的用途肯定是去凑 \ge 2^{p_i} 的数了，中间肯定有个过程是变成了 2^j，那把这个 2^j 用一开始就存在的这个 2^j 替换掉肯定更优。

所以只会存在最多 2m 种取值，设取值为 j 的答案为 ans_j，容易发现 ans 是单调递增的。

考虑判定一个数 $x 能否被凑出来：

• 如果 x=2^t，那么只考虑 \le t 的 a_i，条件就是 \sum 2^{a_i} \ge x。

• 如果 x=\sum\limits_{i=1}^k 2^{b_i}(b_i < b_{i+1})，那么条件就是 \forall i,\sum\limits_{j\le i} 2^{b_j} \le \sum\limits_{a_j \le b_i} 2^{a_j}，容易归纳证明。

把这个条件放到 ans 上去看，对于一个 2^{p_i}，右边的 \sum\limits_{a_j \le p_i} 2^{a_j} 已经知道了，又因为 ans 是单调的，所以如果处理出一个 pos_i 表示最大的 ans_j 使得 ans_j 的 i 后面位置的和 \le \sum\limits_{a_j \le p_i} 2^{a_j}，那么判断 ans 只需要对 pos_{i} 维护前缀 \min 再额外判断一下 j 即可。

考虑咋处理这个 pos，先预处理一个 f_i,g_i 表示把 \le i 的 a 加起来（不进位到 i+1）得到的第 i 位的值和下一个 1 的位置。那么如果 f_{p_i} = 0，pos_i 就没救了，否则如果 >1 那么对于所有后缀都合法，令 pos_i=p_i，=1 可以讨论 g_i 的值通过 pos_{i+1} 递推得到。

复杂度就是预处理 \Theta(n+V)，每次询问 \Theta(m)，总复杂度就是 \Theta(n+V+\sum m)。