注解之于《CHL题解》

这是一篇关于 chl 题解的注解。

建立前缀 Trie 树和后缀 Trie 树。

由下面的讲解可知，对于 ${ a_i }$ 的前缀 $a[1, j)$ 和后缀 $a(j,n]$ 分别建立 Trie。

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

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

设 $x$ 长度为 $l$，则 $bit = a_j[29-l]$。 $a_j[29-l]$ 代表二进制下的第 $29-l$ 位，也即 $a_j \operatorname{>>} (29-l) \& 1$。 $x$ 与 $a_j$ 异或，使得，前后字符串的前半部分都相同。 在前缀树上取 $bit$，则与 $a_j$ 异或之后结果为 $0$。
在后缀树上取 $bit \oplus 1$，则与 $a_j$ 异或之后结果为 $1$。 保证了 $(a_i \oplus a_j) \lt (a_j \oplus a_k)$。

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

流程：从左向右枚举 j。对于每一个 $j$，将前面的数插入 t1，将后面的数插入 t2。复杂度 $n^2$。然后在两颗树上同步查找，复杂度 $30n$。

然而，这需要优化。

优化方向：对于每一个 $j$，不能从无到有地建立两颗树。应当在上一个 $j$ 对应地树上做修改。

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

$$sum_{i, j} = \sum_{|x| = i} sz_{1,p_1,j} \times sz_{2,p_2,j \oplus 1}$$

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

若将根节点作为 30 深度，每向下一层深度减 1。 对于 $j$，答案为 $\sum_{i=29}^{0} sum_{i, a_j[i]}$。

每当 $j \to j + 1$，只需要将 $a_j$ 加入前缀树，修改 $sum_{i, bit}$。将 $a_{j+1}$ 从后缀树中删除，修改 $sum_{i, bit}$。

复杂度是 $\log a_j = 30$。

int n, a[N];
int idx1 = 1, idx2 = 1, t1[30*N][2], t2[30*N][2], sz1[30*N], sz2[30*N];
ll sum[35][2], ans;

//在前缀树中插入
void insert1(int x){
	int p = 1, q = 1;
	for(int dep = 29; dep >= 0; dep --){
		int c = x >> dep & 1;
		if(!t1[p][c]) t1[p][c] = ++idx1;
		if(!t2[q][c]) t2[q][c] = ++idx2;
		sum[dep][c] += 1ll * sz2[t2[q][c^1]];
		p = t1[p][c];
		q = t2[q][c];
		sz1[p]++;
	}
}

//在后缀树中插入
void insert2(int x){
	int p = 1, q = 1;
	for(int dep = 29; dep >= 0; dep --){
		int c = x >> dep & 1;
		if(!t1[p][c]) t1[p][c] = ++idx1;
		if(!t2[q][c]) t2[q][c] = ++idx2;
		sum[dep][c^1] += 1ll * sz1[t1[p][c^1]];
		p = t1[p][c];
		q = t2[q][c];
		sz2[q]++;
	}
}


//在后缀树中删除
void remove2(int x){
	int p = 1, q = 1;
	for(int dep = 29; dep >= 0; dep --){
		int c = x >> dep & 1;
		if(!t1[p][c]) t1[p][c] = ++idx1;
		if(!t2[q][c]) t2[q][c] = ++idx2;
		sum[dep][c^1] -= 1ll * sz1[t1[p][c^1]];
		p = t1[p][c];
		q = t2[q][c];
		sz2[q]--;
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin >> n;
	for(int i = 1; i <= n; i ++) cin >> a[i];
	for(int i = 2; i <= n; i ++) insert2(a[i]);
	for(int i = 2; i < n; i ++){
		insert1(a[i-1]);
		remove2(a[i]);
		ll res = 0;
    //统计答案
		for(int dep = 29; dep >= 0; dep --){
			res += sum[dep][(a[i] >> dep) & 1];
		}
		ans += res;
	}
	cout << ans;
	return 0;
}