题解 P10743 [SEERC2020] AND = OR

提供一种好写的 $O(n \log n \log V)$ 的做法。

先考虑如何对于给定的 $l,r$ 在 $O(n\log n)$ 的复杂度单次求解。不难发现，我们每一次一定是取值域上连续的一段前缀的 $\operatorname{OR}$ 和连续的一段后缀的 $\operatorname{AND}$。排序之后就行了。

类似于 P8421 的做法，不难注意到前缀 $\operatorname{OR}$ 和后缀 $\operatorname{AND}$ 的变化量是 $\log V$ 的。所以我们只需要拎出那些有用的值即可。具体的，我们可以考虑使用 $\log V$ 个 $st$ 表维护区间最大的二进制下第 $i$ 位为 0 的数值和它的位置/区间最小的二进制下第 $i$ 位为 1 的数值和它的位置。不难发现对于一个值它最多只会有两个被加入可能有贡献的数组。所以可能有贡献的数就还是 $\log V$ 级别的。通过预处理可以知道区间内是否有 $\geq 2$ 个那个值。

最后我们直接对着可能的值做暴力。

总的复杂度就是 $O(n \log n \log V + q \log V \log V)$。实践证明瓶颈在前半部分。

至此我们在原数据范围下通过。