这集神了。

先考虑一条链怎么做，即求 $\sum_{i=0}^k a_{x+i}\text{ xor } i$。因为先异或后求和，可以考虑拆位来算，不难发现，$\forall j\in [x,x+2^p)$，$a_j$ 的第 $p$ 位都异或上了 $0$，如果我们将第 $p$ 位去掉并只考虑小于 $p$ 位的贡献，不难发现区间分成了 $[x,x+2^{p-1}),[x+2^{p-1},x+2^p)$ 两个子区间，且他们要解决的问题结构完全相同，这启发我们用倍增去解决问题。

设 $f_{i,j}$ 表示只考虑小于 $j$ 位的值对于 $\sum_{p=0}^{2^j-1} a_{i+p}\text{ xor } p$，设 $g_{i,j,0/1}$ 表示 $1\sim i$ 中第 $j$ 位为 $0/1$ 的位置个数，则有：
$$f_{i,j}=f_{i,j-1}+f_{i+2^{j-1},j-1}+(g_{i+2^{j-1}-1,j-1,1}-g_{i-1,j-1,1}+g_{i+2^j-1,j-1,0}-g_{i+2^{j-1},j-1,0})2^{j-1}$$

这个转移式子大概意思是：对于一个长度为 $2^j$ 的区间，先将这个东西小于 $j-1$ 位的贡献求出来，然后考虑第 $j-1$ 位的贡献，前一半区间只有第 $j-1$ 位为 $0$ 能贡献，后一半只有为 $1$ 才能贡献。

然后我们回到询问，从高到低位拆位算贡献，同时倍增跳，能跳就跳，不能跳就将当前位置到终点部分剩余位置在当前拆的这一位上的贡献算出来。

for(int j=30;j>=0;j--){
	if((k>>j)&1){
		nxt=u+(1<<j);ans+=f[j][u];
		c1=g[1][j][nxt-1]-g[1][j][u-1];
		c0=g[0][j][r]-g[0][j][nxt-1];
		ans+=(c1+c0)*(1ll<<j);u=nxt;
	}else{
		ans+=(g[1][j][r]-g[1][j][u-1])*(1ll<<j);
	}
}

具体的，我们将倍增数组 $f_{i,j}$ 的定义改为从 $i$ 到 $i$ 所在长链往下 $2^j$ 步。对于轻重儿子合并，可以直接将轻儿子的倍增数组加到重儿子的倍增数组上，然后直接对当前点的 $\log$ 个位置倍增。对于 $g$ 也这样更改定义，但是从前缀和变成了后缀和，这样可能会出现很多问题：如倍增数组空位无法合并，后缀和可能访问到不该访问的值，但总而言之是小问题，模仿上面的倍增过程跳下去即可。

时间复杂度为 $O(n\log V)$。