CF1100F Ivan and Burgers
Problem
给定一个长为 \(n\) 的序列，\(Q\) 查询区间异或最大值。
\(1 \le n, Q \le 5 \times 10^{5}\)。
Solution 1
幸运数字的序列版本，但数据范围更大了，三只老哥很难冲得过去。
思考线段树和 ST 表的瓶颈，都是在于过多次数的线性基合并，所以我们的一种思路是优化线性基合并的次数。
这里考虑离线分治（整体二分）。
对于当前分治中心 \(mid\)，处理出其向左的后缀线性基和向右的前缀线性基，然后对所有跨越 \(mid\) 的询问进行单次线性基合并。对于没有跨越 \(mid\) 的询问，递归下去解决。处理前后缀线性基的总时间复杂度为 \(O(n\log{n}\log{V})\)，处理询问的时间复杂度为 \(O(Q\log^{2}{V})\)。
Solution 2
有一个在线的两只老哥做法，没有用到线性基合并。
该做法在普通的异或线性基上，多记录了 取得基元素的位置。
将原序列元素从左到右进行插入，得到 \(n\) 个前缀线性基，在插入过程中，不断将当前位置的元素在线性基中进行替换，使得取得基元素的位置尽量靠后。
查询区间 \([l, r]\) 时，使用第 \(r\) 个版本的线性基，从高位到低位考虑基元素，如果取得当前基元素的位置 \(\ge l\) 且异或上能使答案更优，则异或上该元素。
该贪心过程的正确性是：如果当前元素与线性基线性无关，则会增加线性基维数，不管如何插入，线性基的基元素位置集合都是一样的。
否则，此过程等价于枚举用当前元素替换掉某些基元素（能被替换掉的基元素集合 \(S\) 是确定的，可以证明插入过程可以考虑到集合 \(S\) 中的所有基元素），使得线性基张成的空间不变。这无疑可以使位置换到最优。
如果硬要解释《可以证明》，那我就开始胡言乱语了：
按最高位从大到小考虑基元素 \(\vec{v_{1}}, \vec{v_{2}}, \dots, \vec{v_{m}}\)，记当前元素为 \(w\)，并且钦定 \(w\) 与 \((\vec{v_{1}}, \vec{v_{2}}, \dots, \vec{v_{m}})\) 线性相关。
如果一个基元素 \(\vec{v_{i}}\) 可以被 \(w\) 换出，等价于存在一组组合系数 \(a_{1}, \dots, a_{i - 1}, a_{i + 1}, \dots, a_{m}\)，使得 \(\vec{v_{i}} = w \oplus \bigoplus\limits_{1 \le j \le m, i \neq j}a_{j}\vec{v_{j}}\)。
先考虑 \(\vec{v_{1}}\)，如果 \(w\) 在 \(\vec{v_{1}}\) 对应的最高位为 \(1\)，则 \(w\) 一定可以换出 \(\vec{v_{1}}\)。为什么？因为 \((\vec{v_{1}}, \vec{v_{2}}, \dots, \vec{v_{m}})\) 线性无关，把每个基元素对应一个维度，则 \(\vec{v_{1}}\) 对应的必然是最高位。将 \(\vec{v_{1}}\) 删除后，只会影响到最高位维度的消失；此时加入 \(w\)，必然可以重新扩展最高位所在的维度，也只会影响到最高位所在的维度。反之，如果 \(w\) 在 \(\vec{v_{1}}\) 对应的最高位为 \(0\)，则 \(\vec{v_{1}}\) 的存在是必要的，不能被换出。
假设 \(\vec{v_{1}}\) 可以被 \(w\) 换出，如果要尝试表示出接下来的 \(\vec{v_{i}}\)，则 \(a_{1}\) 必然为 \(1\)，否则消不掉最高位，那么接下来一定不可能表示出 \(\vec{v_{i}}(i = 2, \dots, m)\)。但在实现上的解释略有不同：将线性基中的 \(\vec{v_{1}}\) 换成 \(w\)，并把 \(w \oplus \vec{v_{1}}\) 作为接下来要插入的元素。这步操作在判定式上可以理解为：把 \(a_{1}\) 设置为 \(0\)，并把 \(w\) 替换为 \(w \oplus \vec{v_{i}}\)。
最终，所有能被 \(w\) 换出的基元素，都会被枚举一遍。选择其中位置最小的那个基元素换出即可，这也的确是最优的策略。
// Sea, You & Me
const int N = 5e5 + 5;
const int V = 20;
struct Linear_Base
{
int b[V], pos[V];
void clear()
{
for(int i = 0; i < V; ++i)
b[i] = pos[i] = 0;
}
void insert(int x, int p)
{
for(int i = V - 1; i >= 0; --i)
if(x & (1 << i))
{
if(!b[i]) return b[i] = x, pos[i] = p, void();
else if(pos[i] < p) swap(pos[i], p), swap(b[i], x);
x ^= b[i];
}
}
int query_max(int l)
{
int res = 0;
for(int i = V - 1; i >= 0; --i)
if(b[i] && pos[i] >= l)
chkmx(res, res ^ b[i]);
return res;
}
}LB[N];
int n, Q;
int main()
{
read(n);
LB[0].clear();
for(int i = 1; i <= n; ++i)
{
LB[i] = LB[i - 1];
int x; read(x);
LB[i].insert(x, i);
}
read(Q);
for(int cas = 1; cas <= Q; ++cas)
{
int l, r;
read(l), read(r);
printf("%d\n", LB[r].query_max(l));
}
return 0;
}