题解：XOR and OR

· · 题解

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)。代码很好写，就不放了。