题解：XOR and OR

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

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

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

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

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

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

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