自动搬运

查看原文

来自洛谷，原作者为

	喵仔牛奶 黄昏再美终要黑夜。

搬运于2025-08-24 23:16:01，当前版本为作者最后更新于2025-05-05 18:16:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Solution

考虑拆位。考虑求出按位或和为 $0$ 的区间数，用总区间减去这些就是按位或和为 $1$ 的区间数。

显然，按位或和为 $0$ 等价于区间内全部为 $0$。线段树维护左边和右边最长的 $0$ 连续段长度 $L,R$、区间内按位或和为 $0$ 的区间数 $s$、区间数反转后（$01$ 互换）的积 $w$。

线段树合并信息 $(L,R,s,w)(L',R',s',w')$ 时：

$$\begin{cases} s''=s+s'+R'\times L\\ L''=w\times L'+L\\ R''=w'\times R+R'\\ w''=w\times w' \end{cases} $$

由于有区间 $01$ 反转，还要维护区间 $01$ 反转后的答案。

这样直接做是 $\mathcal O(n\log n\log V)$ 的，无法通过。

考虑求的是异或和，即模 $2$ 的结果。加法和乘法在模 $2$ 意义下等价于按位异或、按位与。因此，将每位的线段树的信息压到一个数里面，合并时将加法改为异或、乘法改完按位与即可。

复杂度 $\mathcal O(n\log n)$。代码很好写，就不放了。