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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
| #include <cstdio>
#include <algorithm>
using namespace std;
template <class Type>
void read(Type &x)
{
char c;
bool flag = false;
while ((c = getchar()) < '0' || c > '9')
c == '-' && (flag = true);
x = c - '0';
while ((c = getchar()) >= '0' && c <= '9')
x = (x << 3) + (x << 1) + c - '0';
flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
x < 0 && (putchar('-'), x = ~x + 1);
x > 9 && (write(x / 10), 0);
putchar(x % 10 + '0');
}
typedef long long LL;
const int N = 2e5 + 10, M = 30, K = 15e6 + 10;
int n, w[N], p[N], f[N], g[N];
int idx, rt[N], id[K], sz[K], tr[K][2];
int fa (int x)
{
return p[x] == x ? x : p[x] = fa(p[x]);
}
void insert (int p, int k, int x)
{
for (int i = M - 1; ~i; i--)
{
int &t = tr[p][k >> i & 1];
!t && (t = ++idx);
sz[p = t]++;
}
id[p] = x;
}
int merge (int x, int y)
{
if (!x || !y)
return x + y;
sz[x] = sz[tr[x][0] = merge(tr[x][0], tr[y][0])] + sz[tr[x][1] = merge(tr[x][1], tr[y][1])];
return x;
}
int query (int p, int q, int k, int &s)
{
for (int i = M - 1; ~i; i--)
{
bool t = k >> i & 1;
if (tr[p][t] && sz[tr[p][t]] > sz[tr[q][t]])
p = tr[p][t], q = tr[q][t];
else
s |= 1 << i, p = tr[p][t ^ 1], q = tr[q][t ^ 1];
}
return id[p];
}
int main ()
{
read(n);
rt[0] = ++idx;
for (int i = 1; i <= n; i++)
read(w[i]);
sort(w + 1, w + n + 1);
n = unique(w + 1, w + n + 1) - w - 1;
random_shuffle(w + 1, w + n + 1);
for (int i = 1; i <= n; i++)
{
p[i] = i;
insert(rt[0], w[i], i);
insert(rt[i] = ++idx, w[i], i);
}
LL res = 0;
for (bool flag = true; flag; )
{
flag = false;
for (int i = 1; i <= n; i++)
g[i] = 0;
for (int i = 1; i <= n; i++)
{
int a = fa(i), s = 0;
int b = fa(query(rt[0], rt[a], w[i], s));
if (a == b)
continue;
(!g[a] || s < f[a]) && (g[a] = b, f[a] = s);
(!g[b] || s < f[b]) && (g[b] = a, f[b] = s);
}
for (int i = 1; i <= n; i++)
{
int a = fa(i), b = fa(g[i]);
if (!g[i] || a == b)
continue;
flag = true;
p[b] = a;
res += f[i];
merge(rt[a], rt[b]);
}
}
write(res);
return 0;
}
|