题意：给两个序列[a, a + n), [b, b + n)，求所有数(ai + bj)的异或和，i,j∈[0,n)。
思路：这个题思路比较巧妙，不难但是难想到。BC上的题解讲得非常清楚了，我就直接copy过来了吧
我们考虑两个数A，B。
为了描述方便，我们设[P]的值为：当表达式P的值为真时，[P]=1，否则[P]=0
我们现在考虑计算[(A+B)and(2i)>0]
首先我们将A,B都对2i+1取模，显然这样是不会影响答案的
则有一个十分显然的等式：
[(A+B)and(2i)>0]=[(A+B)≥(2i)]−[(A+B)≥(2i+1)]+[(A+B)≥(3∗2i)]
这个式子相当容易理解，这里不多述了
考虑每一位对答案的贡献是独立的，我们每一位分开做
于是现在问题变成了：给定数组A,B，求满足Ai+Bj≥limit的数对个数
我们可以将A,B排序后，直接O(n)计算即可
然而排序是O(nlogn)的，这样总复杂度就是O(nlognlogA)了，无法通过此题
于是这里有个小技巧
我们从高位往低位做，现在我们要实现的是：将A中每个数对P取模后将A排序
我们发现A会被分成两段，一段小于P，一段大于等于P，只有后面一段要取模，我们可以取模后直接将这两段归并，复杂度是O(n)的
时间复杂度：O(nlogA+nlogn)
下面的代码就是根据题解写的，个人感觉也非常清晰了：
| 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263 | #pragma comment(linker, "/STACK:10240000,10240000")#include <iostream>#include <cstdio>#include <cstring>#include <cstdlib>#include <vector>#include <algorithm>#include <queue>using namespace std; const int maxn = 1e5 + 7; int n;long long a[maxn], b[maxn]; void sort(long long *a, long long md) { int pos = n; for (int i = 0; i < n; i ++) { if (pos == n && a[i] >= md) pos = i; a[i] = a[i] & (md - 1); } inplace_merge(a, a + pos, a + n);} bool solve(long long limit) { long long ans = 0; int that = n - 1; for (int i = 0; i < n; i ++) { while (that >= 0 && a[i] + b[that] >= limit) that --; ans += n - 1 - that; } return ans & 1;}int main() {#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin);#endif // ONLINE_JUDGE int T, cas = 0; cin >> T; while (T --) { cin >> n; for (int i = 0; i < n; i ++) { scanf("%I64d", a + i); } for (int i = 0; i < n; i ++) { scanf("%I64d", b + i); } sort(a, a + n); sort(b, b + n); long long ans = 0; for (int i = 61; i >= 0; i --) { sort(a, (long long)2 << i); sort(b, (long long)2 << i); long long res = solve((long long)1 << i) ^ solve((long long)2 << i) ^ solve((long long)3 << i); ans |= res << i; } printf("Case #%d: %I64d\n", ++ cas, ans); } return 0;} |
