考虑最后的集合是否为可重集对答案没有影响,我们可以把相邻或重合的区间合并

  • 对于一个连续区间的异或和,其实就是连续奇数的异或和,对于每一个二进制位进行分析,发现他是有循环节的,故对于每一个二进制位进行分析,以 $O(\log \ \texttt{值域})$ 的复杂度计算出答案。

  • 对于相邻的两个区间,我们可以 $O(1)$ 直接计算

故把这些区间放到 std::set / std::vector / 平衡树 / 线段树上。每次暴力合并区间。由于每个区间最多被删一次,也最多被加一次,总复杂度为 $O(n \log n)$ 。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×