CF1261F Xor-Set

发表于 分类于 ， ， 阅读次数：

题意：给出集合 。被表示为 个区间 的并集，集合 类似。

记 求 中元素的和。

，，时限 。

模仿 Luogu3791 的思想，一个区间 可以被拆分为 个集合，形如“钦定若干高位，剩余低位随意”。我们称这种集合是“整区间”。

这可以用线段树来实现。我们会得到 个整集合。

两个整区间异或所能产生的数是一个区间，那么可以两两枚举生成一系列区间，然后区间求并。

会有 个生成区间，如果使用 std::sort 求并,复杂度为 ,不可承受。

进一步观察性质。

若两个区间分别钦定高 位，高 位，不妨设 。能够发现，答案区间只会钦定 位。 多出来的部分是没有影响的。若把 保留前 位的限制得到的答案仍是相同的。

在线段树上，若某个点本身没有被覆盖，但是下面有被覆盖的点，则称该点为虚点。

两个虚点之间是不能贡献的，虚实，实实，都是可以贡献的。

由上面的结论，只需要考虑同层之间的贡献。生成区间被降至 个，可以通过。复杂度 。

实现：先存下 的所有拆出来的实区间，按照深度分类。 把访问到的虚实区间与同深度的 区间组合即可。

还需反过来再做一次。