线性基
概念
设数集$T$的范围为$[1,2^n−1]$。
$T$的线性基是$T$的一个子集$A=\{a1,a2,a3,…,an\}$。
$A$中元素互相$xor$所形成的异或集合，等价于原数集$T$的元素互相$xor$形成的异或集合。
$A$可以看成是$T$的压缩。
性质
线性基有一些性质：
- 线性基的异或集合中不存在$0$。也就是说，$A$是$T$中的极大线性无关组，同时$A⊆T$。
- 线性基中每个元素的异或方案唯一，也就是说，线性基中不同的异或组合异或出的数都是不一样的。这个与性质1其实是等价的。
- 线性基的二进制最高位互不相同。
- 如果线性基是满的，它的异或集合为$\{1,2,3…2^n-1\}$。
- 线性基中元素互相异或，异或集合不变。
维护
插入
如果向线性基中插入数$x$，从高位到低位扫描它为1的二进制位。
扫描到第$i$位时，如果$a_i$不存在，就令$a_i=x$，否则$x=x⊗a_i$。
$x$的结局是，要么被扔进线性基，要么经过一系列操作过后，变成了$0$。
合并
将一个线性基暴力插入另一个线性基即可。
查询
最大值
从高位到低位扫描线性基。
如果异或后可以使得答案变大，就异或到答案中去。
最小值
最小值即为最低位上的线性基。
k小值
根据性质3。
我们要将线性基改造成每一位相互独立。
具体操作就是如果i<j，$a_j$的第$i$位是$1$，就将$a_j$异或上$a_i$。
经过一系列操作之后，对于二进制的某一位$i$。只有$a_i$的这一位是$1$，其他都是$0$。
所以查询的时候将$k$二进制拆分，对于$1$的位，就异或上对应的线性基。
最终得出的答案就是$k$小值。
模板
样例输入
一个整数N，后面N行待插入的数值
6
5
23
4
12
2
9
样例输出
一个最大的xor值和一个最小的xor值
31 1
下面给出完整模板：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
104
105
106
107
108
using namespace std;
class LinearBase
{
public:
long long d[61], p[61];
int cnt;
LinearBase()
{
memset(d,0,sizeof(d));
memset(p,0,sizeof(p));
cnt=0;
}
bool insert(long long val)
{
Fordowni
{
if (val & (1ll << i))
{
if (!d[i])
{
d[i] = val;
break;
}
val ^= d[i];
}
}
return val > 0;
}
long long Querymax()
{
long long res = 0;
Fordowni
{
if ((res ^ d[i]) > res)
res ^= d[i];
}
return res;
}
long long Querymin()
{
long long res = 0;
Forupi //这边不要写成Fordowni
if (d[i])
return d[i];
}
void rebuild()
{
Fordowni
{
for (register int j = i - 1;j >= 0;j--)
{
if (d[i] & (1ll << j))
{
d[i] ^= d[j];
}
}
}
Forupi
{
if (d[i])
p[cnt++] = d[i];
}
}
long long kthquery(long long k)
{
rebuild();
long long ret = 0;
if (k >= (1ll << cnt))
return -1;
Fordowni
if (k & (1ll << i)) //不同的写法：(k >> i) & 1
ret ^= p[i];
return ret;
}
};
LinearBase merge(const LinearBase &n1,const LinearBase &n2)
{
LinearBase ret = n1;
Fordowni
if (n2.d[i])
ret.insert(n2.d[i]);
return ret;
}
LinearBase A;
int N;
int main()
{
cin >> N;
for (register int i = 1; i <= N; ++i)
{
long long x;
cin >> x;
A.insert(x);
}
cout << A.Querymax() << " " << A.Querymin() << endl;
return 0;
}