题解

思路

对非空兴趣点集合 $S$，若要求 $S$ 中所有点都不被坐标为 $x$ 的灯笼照亮，则灯笼功率必须小于 $\min_{y\in S}|x-y|$，恰有这么多种选择。令空集对应的选择数为 $d+1$。容斥后，答案是这些选择数在所有灯笼上的乘积之和。

做法

子任务 1：枚举功率

对每次询问，把临时灯笼加入数组，递归枚举每个灯笼的 $0\ldots d$ 功率并检查兴趣点覆盖。复杂度为 $O(q(d+1)^{n+1}m)$。

子任务 2：直接子集容斥

枚举 $S\subseteq[0,m)$。对每个原有灯笼计算所有子集的最近兴趣点距离，并乘入 prod[S]；对每次询问再计算临时灯笼的距离。答案为

$$\sum_S(-1)^{|S|}\operatorname{prod}[S]\cdot\operatorname{dist}(f,S).$$

用最低位递推子集最小值，复杂度为 $O((n+q)2^m)$，空间为 $O(2^m)$。

子任务 3：乘法差分与子集变换

把兴趣点排序。固定灯笼 $x$，随着所选兴趣点集合改变，最近距离只会在某个兴趣点成为最近点时变化。对每个兴趣点 $i$，二分找到与它至少同远的左右边界，把距离因子乘到一个掩码，并在去掉位 $i$ 的掩码乘逆元。随后做乘法子集变换，即可在 $O(m)$ 次事件内表达该灯笼对所有子集最近距离的贡献。

汇总全部原有灯笼后，先做乘法变换还原各子集乘积，给奇数大小子集取负，再做加法子集变换。每次询问只需枚举哪个兴趣点是临时灯笼的最近点，并用两个预处理掩码值之差统计贡献。

总复杂度为 $O((n+q)m+m2^m+d\log MOD)$，空间复杂度为 $O(d+2^m)$。

复杂度

三层算法的时间复杂度依次为 $O(q(d+1)^{n+1}m)$、$O((n+q)2^m)$、$O((n+q)m+m2^m+d\log MOD)$；空间复杂度依次为 $O(n+m)$、$O(2^m)$、$O(d+2^m)$。

正确性

容斥式逐一减去至少一个指定兴趣点未被照亮的方案，因而恰好保留全部兴趣点均被照亮的分配。中档算法直接计算该式。满分算法只把同一组最近距离乘积用乘法差分和子集变换重新组织，并按最近兴趣点分拆临时灯笼贡献，所以与容斥式完全等价。