自动搬运

查看原文

来自洛谷，原作者为

	Created_equal1 **

搬运于2025-08-24 21:48:37，当前版本为作者最后更新于2016-10-09 19:12:10，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

方法1：

预处理每个点到根节点的xor值之后就变成了一个路径上任意两点xor的和，这个我们可以通过维护某一位是1的个数，然后分别统计贡献来做到。至于修改操作，就等价于一个子树某一位翻转修改。具体用树链剖分+线段树实现即可。

方法2：

考虑序列上的做法，我们可以用线段树维护一发左右子树的答案和每一位的情况来合并答案。把扔到树上去只要加上树链剖分即可。这种方法写起来比第一种方法麻烦一些。

两种做法的复杂度都是O(nlog^2n*w)的。