题解：P10408 「SMOI-R1」Apple

迟暮天复明 · 2024-09-09 21:37:26 · 题解

前情提要

如果有人认为我写的比官方题解烂我直接反手撤下这篇题解。

前置知识：高维前缀和

你考虑假设我们直接高位前缀和维护了这个子集和，那么查询操作的确是 O(1) 了，但是改完一个数之后就得重新 O(2^N) 跑一遍高位前缀和，然后你就寄了。

所以考虑把两个操作平衡到都用 O(2^{N/2}) 时间。这说明我们查询操作的时候可以枚举 2^{N/2} 个数，修改的时候只能修改 2^{N/2} 个数。

考虑设 F_S 表示前 N/2 位和 S 完全一致，后 N/2 位是 S 子集的所有数字之和。

那么对于查询操作，我们只需要对着 X 的前 N/2 位枚举子集，然后累加即可。

对于修改操作，因为 X 的前 N/2 位是钦定的，所以就相当于在他的后 N/2 位上跑高维前缀和。

总时间复杂度 O(Q2^{N/2})，对时间限制的谴责，代码。