题解 - 异或（xor.cpp）

题意

求序列 $a$ 中所有数 $\oplus p_i$ 后，逆序对的数量。 $1 \leq n,m \leq 10^5, 1 \leq a_i, p_i \leq 2^{32}$

题解

本题本来写了朴素算法，期望得分$30pts$，结果挂了。直到现在还不知道为什么挂了。

现在来讲正解。

异或是按位来运算的，而数据范围又这么大，考虑一种按位处理的做法。

可以观察到，逆序对的产生或者消失先取决于位数大的数字，对于一个位上来说，异或的结果都一样，所以这些大的位数如果被异或了，下一步产生或消失的异或数量取决于更小的位置上的值。所以对于每个位上，其实都可以单独处理贡献，那么我们让这个序列去异或上 $2^1, 2^2, 2^3 … 2^{32}$，然后在处理询问时，只要明确哪些位上面做了异或，最后统计答案即可。

tips:如果你用TrieTree维护过逆序对，这个会好想一些

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n, m, q;
ll a[N], b[N], c[N];
ll cnt;
inline void msort(int l, int r) {
	if(l == r) return;
	int mid = (l + r) >> 1;
	msort(l, mid); msort(mid + 1, r);
	int i = l, j = mid + 1, k = l;
	while(i <= mid && j <= r) {
		if(a[i] <= a[j]) b[k++] = a[i++];
		else b[k++] = a[j++], cnt += mid - i + 1;
	}
	while(i <= mid) b[k++] = a[i++];
	while(j <= r) b[k++] = a[j++];
	for(int i = l; i <= r; i++) {
		a[i] = b[i];
	}
}

int main()
{
	freopen("xor.in", "r", stdin);
	freopen("xor.out","w", stdout);
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) {
		scanf("%lld", &c[i]);
		a[i] = c[i];
	}
	ll tmp = 1;
	ll ans[50];
	cnt = 0;
	msort(1, n);
	ans[0] = cnt;
	for(int i = 1; i <= 33; i++) {
		for(int j = 1; j <= n; j++) {
			a[j] = c[j] ^ (tmp);
		}
		// cout << endl;
		cnt = 0;
		msort(1, n);
		ans[i] = cnt;
		tmp <<= 1;
	}
	ll q, ret = 0;
	while(m--) {
		scanf("%lld", &q);
		ret = ans[0];
		for(int i = 0; i <= 32; i++) if(q & (1LL << i)) ret += ans[i + 1] - ans[0];
		printf("%lld\n", ret);
	}
	return 0;
 }