跃迁引擎启动

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;
}