线性基
概念：
线性基就是一组基（啊说通俗一点点就是一组数字），这一组基相互进行异或操作能够表示出给定原集合的所有异或和，我们一般选择最简单的一组。
可用于每一个亦或和的排名以及每个排名对应的异或和。
构建
线性基的构建相当的简单，对于每次给定的一个数 a，对于线性基从大到小考虑，设当前考虑的位置为 \(i\) ，如果 \(a\) 的第 \(i\) 位是 \(1\) ，进行如下操作：
- 如果第 \(i\) 个位置已经被占数字 \(b\) 了，我们让 \(a=a \oplus b\) ，然后继续考虑下一个位置。
- 如果第 \(i\) 个位置没有被占领，那么让 \(a\) 占领这个位置，然后跳出循环。
考虑这样做为什么是正确的。
假设线性基原有数字 \(a\) ，对于待插入的数字 \(b\) 。
- 如果 \(b\) 没有异或上 \(a\) ，那么两个数字在线性基中都存在，正确性显然。
- 如果 \(b\) 异或上了 \(a\) ，也就是线性基中存在数字 \(c=a \oplus b\) ，那么 \(b=a \oplus c,a\oplus b =c\)
推广到多个也是正确的。
代码如下
inline void Insert(LL v) {
for(int i=62;i>=0;i--)
if(v>>i & 1) {
if(!a[i]) { a[i]=v; return ; }
else v^=a[i];
}
}
简化
上述方法构造出来的线性基可以进一步进行简化，我们简化的目的，就是让每一位最多只在线性基中一个位置上为 \(1\) ，这样就可以消除彼此之间的干扰，做与排名有关的工作。
正确性同上
代码如下
inline void Build() {
for(int i=0;i<=62;i++)
if(a[i])
for(int j=i+1;j<=62;j++) if(a[j]>>i & 1) a[j]^=a[i];
for(int i=0;i<=62;i++) ans^=a[i];
}
求排名
简化之后，每一位至多只会在线性基中的一个位置上为 \(1\) ，且位置已经排好了序，每个位置的数我们都可以选择异或上它或者不这么做，想想就跟二进制数非常有关，如果排名 \(k\) 的从大到小第 \(i\) 位为 \(1\) 的话，我们就异或上线性基从大到小第 \(i\) 个位置的数。注意特别考虑下 \(0\) 即可。
inline int Qry(int v) {
int rk=0;
for(int i=0;i<=idx;i++)
if(v>>o[i] & 1) rk+=1<<i;
return ++idx, rk;
}