Codeforces 1055F Tree and XOR 题解

题面

给定一个长度为 $n$ 的序列求两两异或值的第 $k$ 小。

其中 $2 \le n \le 10^6$。

分析

显然需要建一棵字典树出来。

在字典树上从大到小地往下爬,如果当前 $k$ 大于该位异或值为 $0$ 的对数,那么表示这个位置应该选 $1$,否则选 $0$。

但是把字典树建出来空间是不够的,考虑将字典树滚动掉。

从高位往低位枚举,维护序列每个点在字典树上爬的标号,这个标号是滚动的,并且记录每个结点的大小。

再维护序列上每个位置与哪个结点配对,计算每层的大小时,累加一下选择与这个数字在该位异或为 $0$ 的结点总数。

根据大小关系,更新答案和 $k$ 值,并将每个结点的配对位置往下爬。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ms(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn = 1000000 + 5;

int n, tot, a[maxn], b[maxn], ch[maxn][2], siz[maxn];
ll k, w[maxn];

int main(){
scanf("%d%I64d", &n, &k);
for (int i = 2; i <= n; i++){
int f; ll x; scanf("%d%I64d", &f, &x);
w[i] = w[f] ^ x;
}
for (int i = 1; i <= n; i++) a[i] = b[i] = 1;
ll ans = 0;
for (int t = 61; t >= 0; t--) {
for (int i = 1; i <= tot; i++) ch[i][0] = ch[i][1] = siz[i] = 0;
tot = 0; ll s = 0, flag = 0;
for (int i = 1; i <= n; i++) {
int b = w[i] >> t & 1;
if (ch[a[i]][b]) a[i] = ch[a[i]][b];
else a[i] = ch[a[i]][b] = ++tot;
siz[a[i]]++;
}
for (int i = 1; i <= n; i++) {
s += siz[ch[b[i]][w[i] >> t & 1]];
}
if (s < k) k -= s, flag = 1, ans += 1ll << t;
for (int i = 1; i <= n; i++) {
b[i] = ch[b[i]][(w[i] >> t & 1) ^ flag];
}
}
printf("%I64d", ans);
return 0;
}