洛谷P4839“P的桶”
•题意
有 m 个桶，依次编号 1~m；
初始，这 m 个桶全部为空桶；
给你 n 次操作，每次操作有两种：
（1）1 k x : 往 k 桶中加入数
（2）2 l r : 查询 $[l,r]$ 对应数的异或最大值；
•题解
很常规的一道线性基题目；
用线段树维护，对于操作 1，找到第 k 个桶在线段树中的位置 pos，将 x 插入到 pos 对用的线性基中即可；
pushUp(pos) 的话，你可以选择每次向上回溯的时候将 pos 的左右儿子的线性基合并；
其实不用这么做，因为每次只在 k 处添加一个数，直接在 update() 回溯的时候，将当前位置 pos 的线性基中插入 x 即可；
•Code
CodeForces1100F"Ivan and Burgers"
•题意
给你 n 个数，m 此操作，每次操作选择一个区间，求这个区间异或最大值；
•题解
感觉这道题上一道题差不多，都是求区间异或最大值；
但是，此题的数据范围 $nleq 5^5$，用线段树维护线性基的方式是会超时的；
解法1：离线处理
将所有询问收集起来，并按照 r 升序排列；
边插入 $a_i$ 边判断 i 是否为当前询问的右端点；
插入的时候，记录两个数值 $base_i,p_i$，表示第 $p_i$ 个数 $a_{p_i}$ 在通过 $Insert()$ 操作时，插入到了 $base_i$ 中；
每次插入第 i 个数 $a_i$ 时，优先让高位的 1 用当前的位置 i 来表示；
解法2：在线处理
理解了离线处理的方式，在线处理很容易就能理解；
就是在之前的基础上多开了一维；
定义 $base[i][]$ 表示按照上述离线方式插入前 i 个数后形成的基底，$p[i][]$ 表示按照上述离线方式插入前 i 个数后，$base[i][]$ 对应的插入下标；
HDU3949"XOR"
•题意
给你 n 个数，q 此询问，每次询问给出一个数 k；
求经这 n 个数异或后得到的第 k 小的数，不存在输出 -1；
•题解
首先将这 n 个数插入到线性基 $base$ 中；
然后，需要改造 $base$，使其满足如下要求：
对于任意存在于线性基的二进制位 i，至多只有一个 $base_j$ 满足第 i 位为 1。
将改造后的线性基中的非零值按照升序的方式存入 $th$ 中；
1 vector<ll >th; 2 void reBuild() 3 { 4 th.clear(); 5 for(int i=60;i >= 0;--i) 6 for(int j=i-1;j >= 0;--j) 7 if(base[i]>>j&1) 8 base[i] ^= base[j]; 9 for(int i=0;i <= 60;++i) 10 if(base[i]) 11 th.push_back(base[i]); 12 }这 n 个数共有 $siz=th.size()$ 个非零基底；
那么，共有 $2^siz -1$ 个组合方式，所以，这 $siz$ 个非零基底共可形成 $2^siz-1$ 个不同的数；
由于线性基是不能表示 0 这个数的，所以需要单独判断这 n 个数是否可以通过异或得到 0；
如果可以，那么这 n 个数经过异或可得到 $2^siz$ 个不同的数，反之，仅能得到 $2^siz-1$ 个不同的数；
判断是否包含 0，直接判断 siz 和 n 的大小关系即可；
如果 siz == n ，说明这 n 个数全部插入到了线性基中，也就意味着得不到 0；
反之，可以得到 0；
得到 $th$ 后，如何得到第 k 小的数呢？
公式：$kth=oplus k_icdot th_i$，其中 $k_i$ 指的是 k 转化成二进制后的第 i 位；
不难用二进制的思想证明；
•题目变形
给你 n 个数，q 次询问，每次询问给出三个数 $l,r,k$；
求 $[l,r]$ 区间异或第 k 小的值，不存在输出 -1；
•题解
$[l,r]$ 区间的第 k 小，你需要知道的是 $a_l,a_{l+1},cdots ,a_r$ 这 $r-l+1$ 个数重构后的线性基；
每次都从 l 循环到 r 求解肯定不行；
借鉴上述 CodeForces1100F 在线的思想，提前预处理出 $[1,r]$ 的线性基即可；
每次重构的时候，只需遍历 $base$ 中有限的 60 个数就行；
时间复杂度 $O(mcdot 60^2)$