https://ac.nowcoder.com/acm/contest/110811/G
题意概述
给定两个长度为 \(n\) 的数组 \(a,b\) 和两个参数 \(k_1,k_2\)，求满足：
-
\(i \lt j\)
-
\(k_1 \oplus a_i \oplus a_j \lt k_2 \oplus b_i \oplus b_j\)
的点对数量。
思路
记 \(k_1 \oplus a_i \oplus a_j = X\)，\(k_2 \oplus b_i \oplus b_j = Y\)。原不等式相当于在 \(X \oplus Y\) 的最高有效位 \(d\) 上，\(X\) 在该位上为 \(0\)，\(Y\) 在该位上为 \(1\)。
\(X \oplus Y\) 在 \(d\) 之前的位上为 \(0\)。\(X\) 的第 \(d\) 位为 \(0\)，即 \(k_1 \oplus a_i \oplus a_j\) 第 \(d\) 位为 \(0\)。
\(X \oplus Y\) 的表达中可以将 \(i,j\) 分离，考虑 \(trie\) 树，插入 \(a_i \oplus b_i\)。需要知道 \(X\) 是否为 \(0\)，统计 \(a_i\) 在该位为 \(0\) 和为 \(1\) 的数量。
在 \(trie\) 树上累加贡献即可，跳转时走让 \(X \oplus Y\) 在该位为 \(0\) 的边，如果存在让 \(X \oplus Y\) 在该位为 \(1\) 的边，就以该位为最高位计算一次贡献。
时间复杂度 \(\mathcal{O}(32n)\)。
代码
//author:kzssCCC#include <bits/stdc++.h>
using namespace std;
using ll = long long;void solve(){int n,k1,k2;cin >> n >> k1 >> k2;vector<int> a(n+1);for (int i=1;i<=n;i++){cin >> a[i];} vector<int> b(n+1);for (int i=1;i<=n;i++){cin >> b[i];}vector<array<int,2>> next{{-1,-1}};vector<array<int,2>> cnt{{0,0}};ll res = 0;for (int i=1;i<=n;i++){{int u = 0;for (int j=31;j>=0;j--){if (next[u][((a[i]^b[i]^k1^k2)>>j&1)^1]!=-1){res += cnt[next[u][((a[i]^b[i]^k1^k2)>>j&1)^1]][(a[i]^k1)>>j&1];}if (next[u][(a[i]^b[i]^k1^k2)>>j&1]!=-1){u = next[u][(a[i]^b[i]^k1^k2)>>j&1];}else break;}}{int u = 0;for (int j=31;j>=0;j--){int cj = (a[i]^b[i])>>j&1;if (next[u][cj]==-1){next.push_back({-1,-1});next[u][cj] = next.size()-1;cnt.push_back({0,0});}cnt[next[u][cj]][a[i]>>j&1]++;u = next[u][cj];}}}cout << res << '\n';
}int main(){ios::sync_with_stdio(false);cin.tie(0);int t = 1;// cin >> t;while (t--) solve();return 0;
}