题意

给你$10^5$个数${A_i}$，问满足$i < j < k$且有$A_i \oplus A_j < A_j \oplus A_k$的三元组$(i, j, k)$个数。

思路

考虑在何种情况下$A \oplus B < A \oplus C$

考虑下面的例子：

B = 10101xx
C = 10100xx

注意到写有”x“的位数不影响答案，考虑$B$,$C$最高在$2^k$位不同，则有$A$在$2^k$位也一定不同。反之亦然。

这是因为异或运算满足消去率。且有$1 \oplus 0 = 0$, $0 \oplus 0 = 1 \oplus 1 = 0$

解决

显然，我们可以很方便地维护每个对于$i < k$的$i$中，某一位为0或者为1的个数有多少个。但是要求$i < j < k$，于是自然想到了计数然后减去，即小于$k$的减去小于等于$i$的某位为0/1的数的个数即可。两者相减即为答案，而两者均可加，故可以考虑使用某种数据结构快速维护。

那么接下来即思考如何前缀为某个串且“某位恰不同”的数的个数。这样我们得到了Trie树的模型。考虑用Trie树维护转换为二进制串的数。

考虑在Trie树上的节点维护下面两个信息：

前缀为某个串的数的个数
前缀为某个串，该位为0/1的数的个数

那么对于每次询问，只需要在Trie树上走一边就可以得到答案。

Code

耗时: 702 ms

内存: 38828 K

#include <bits/stdc++.h>

using namespace std;

struct trienode{
	int s[2];
	long long cnt[3];
}trie[31 * 500000];

long long siz[31][2];
int num[31];

int totid, rt;

int get_newnode()
{
	totid++;
	memset(&trie[totid], 0, sizeof(trienode));
	return totid;
}

long long get_ans()
{
	int cur = rt;
	long long ans = 0;
	for (int i = 0; i < 30; i++)
	{
		int s0 = trie[cur].s[0];
		int s1 = trie[cur].s[1];
		if (num[i] == 0)
		{
			ans += siz[i][1] * trie[s1].cnt[2] - trie[s1].cnt[1];
			cur = s0;
		}
		else
		{
			ans += siz[i][0] * trie[s0].cnt[2] - trie[s0].cnt[0];
			cur = s1;
		}
	}
	return ans;
}

void insert_ai()
{
	int cur = rt;
	for (int i = 0; i < 30; i++)
	{
		if (trie[cur].s[num[i]] == 0)
			trie[cur].s[num[i]] = get_newnode();
		cur = trie[cur].s[num[i]];
		trie[cur].cnt[2]++;
		trie[cur].cnt[0] += siz[i][0];
		trie[cur].cnt[1] += siz[i][1];
	}
}

void sol()
{
	memset(siz, 0, sizeof siz);
	totid = 0;
	rt = get_newnode();
	int n;
	scanf("%d", &n);
	long long ans = 0;
	for (int i = 1; i <= n; i++)
	{
		int x;
		scanf("%d", &x);
		for (int i = 0; i < 30; i++) num[30 - i - 1] = ((x >> i) & 1);
		ans += get_ans();
		for (int i = 0; i < 30; i++) siz[i][num[i]]++;
		insert_ai();
	}
	printf("%lld\n", ans);
}

int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
		sol();
	return 0;
}