XOR

建立 Trie。

建立前缀 Trie ，后缀 Trie。

枚举 $j$， 前缀包含 $\forall 1\le x<j, a_x$，后缀就是 $\forall j < x \le n, a_x$。

前缀 Trie 和后缀 Trie 建立起来，分别记作 ： $t_1, t_2$。不难发现答案即为： 同一个前缀 $x$，令其在 $t_1, t_2$ 中的结尾下标为 $p_1, p_2$，答案即为 $\sum\limits_{x}{sz_{1, son_{p_1, bit} \times sz_{2, son_{p_2, bit \oplus 1}}}}$。 $bit$ 是去除与前缀 $x$ 相同长度的前缀后，他的位。

相当于同一个前缀 $x$，令这个前缀相同，随后到这一位恰好左边小，右边大。

随后，不难发现这是可以 BF 平方的。

// 此处 0 是根，调用： dfs1(29, 0, 0, a[i]) ;
void dfs1(int dep,int p, int q, int x)
{
	if(dep != 29 && (p == 0 || q == 0)) return ;
	int bit = (x >> dep) & 1 ;
	ans += v1[t1[p][bit]] * 1ll * v2[t2[p][!bit]] ;
	if(dep < 0) return ;
	dfs1(dep-1, t1[p][0], t2[q][0], x) ;
	dfs1(dep-1, t1[p][1], t2[q][1], x) ;
}

然而，这需要优化。不难发现这可以记录 $sum_{i, j}$ 表示深度为 $i$，$bit = j$ 的和。

就是固定了深度和位权，维护总和。不难发现，由于修改次数是对数的，复杂度正确。

Trie 树以后以 $1$ 为根。