Xor

$\text{题意}$：
给定一个序列长为 $n$ 的 $\{a\}$，有 $m$ 次操作，每次操作读入一个数 $p$，求 $\{a\oplus p\}$ 的逆序对个数。
对于所有数据 $n,m \le 10^5$。

$\text{Solution}$ ：
我们发现两个数大小不同的实质是其第一个最高不同的二进制位一个是 $0$，一个是 $1$。这启示我们 $O(n^2)$ 暴力的做法：两两枚举数对，记录不同的最高二进制位，复杂度 $O(n^2 \log V + m \log V)$。

考虑优化这个过程，$Tire$ 树上枚举即可。

 1 #include <bits/stdc++.h>
 2 
 3 typedef long long ll;
 4 const int N = 2e5 + 50;
 5 using namespace std;
 6 
 7 #define gc getchar
 8 ll read() {
 9     ll x = 0; char c = gc();
10     while(!isdigit(c)) c = gc();
11     while(isdigit(c)) x = x * 10 + (c ^ 48), c = gc();
12     return x;
13 }
14 
15 int ch[N*20][2], cnt, rot;
16 ll sm[N*20], a[N];
17 ll vl[2][33];
18 
19 void insert(int& rt, int i, int ip) {
20     if(!rt) rt = ++cnt;
21     if(!~i) {sm[rt]++;return;} 
22     int to = (a[ip] >> i) & 1;
23     vl[to][i] += sm[ch[rt][to ^ 1]];
24     insert(ch[rt][to], i - 1, ip);
25     sm[rt] = sm[ch[rt][to]] + sm[ch[rt][to ^ 1]];
26 }
27 
28 int n, m;
29 
30 int main() {
31     freopen("xor.in","r",stdin);
32     freopen("xor.out","w",stdout);
33     cin >> n >> m;
34     for(int i = 1; i <= n; ++i) a[i] = read();
35     for(int i = 1; i <= n; ++i) {
36         insert(rot, 32, i);
37     }
38     for(int i = 1; i <= m; ++i) {
39         ll p = read(), as = 0;
40         for(int i = 0; i <= 32; ++i) {
41             as += vl[p & 1][i];
42             p >>= 1;
43         }
44         printf("%lld\n", as);
45     }
46     return 0;
47 }