静态区间，选取任意个数使得它们的异或和最大
\(n,\ m\leq5\times10^5,\ a_i\in[0,\ 10^6]\)
lxl ST表，线性基
如果暴力维护线性基，线段树时间复杂度为 \(O(n\log^2n)-O(\log^3n)\)
由于重复元素对答案没有影响，于是可以用 ST表 维护，时间复杂度为 \(O(n\log^3n)-O(\log^2n)\)
两种做法都无法通过本题。
如果沿用这个思路，瓶颈显然在线性基合并的 \(O(\log^2n)\) 上，无法再加优化
线段树做法显然无法再加拓展（和 lxl ST表时间复杂度一样的猫树空间复杂度多一只 \(\log\) ），于是考虑拓展 ST表 做法
常见的 RMQ 有 ST表 的 \(O(n\log n)-O(1)\) 的做法，但 \(O(n)-O(1)\) 的标准RMQ很难写、常数较大，且无法解决本题，于是可以考虑在随机数据下期望 \(O(n)-O(1)\) 的 lxl ST表
分块，大小设为 \(x\)
预处理每个块两端到块内每个点的前缀 \(\max\) 和后缀 \(\max\)
预处理块间ST表
若查询 \([l,\ r]\) ，且 \(l,\ r\) 分别在块 \(a,\ b\) 中
比如说我查l，r，这两个分别在块a，b中
则查块 \(a,\ b\) 之间的 RMQ ，以及 \(l\) 在 \(a\) 块的后缀 \(\max\) 和 \(r\) 在 \(b\) 块的前缀 \(\max\)
当 \(l,\ r\) 在同一块中时，暴力求解
可以取 \(x=\log n\) ，当 \(l,\ r\) 不在同一块中时，这个算法是 \(O(1)\) 的
摘自
如上维护，预处理块中前缀后缀线性基 \(O(n\log n)\) ，块间ST表线性基 \(O(\frac{n}{x}\log n\log^2n)=O(n\log^2n)\)
若 \(l,\ r\) 在同一块中，将 \([l,\ r]\) 中的元素暴力插入线性基， \(O(x\log n)=O(\log^2n)\) ；若 \(l,\ r\) 不在同一块中，合并前缀后缀块间三个线性基 \(O(\log^2n)\)
综上所述，时间复杂度 \(O(n\log^2n)\) ，空间复杂度 \(O(n\log n)\) 可能还需要卡卡常
代码
#includeusing namespace std;const int maxn = 5e5 + 10, maxm = 7850, base = 63;int n, m, tot, lg[maxm], a[maxn];#define get(x) (((x) + base) >> 6)struct linear_base { int a[20]; inline void clr() { memset(a, 0, sizeof a); } inline void ins(int x, int lim = 19) { for (int i = lim; ~i; --i) { if (x >> i & 1) { if (!a[i]) { a[i] = x; return; } x ^= a[i]; } } } inline int query() { int res = 0; for (int i = 19; ~i; --i) { if ((res ^ a[i]) > res) res ^= a[i]; } return res; }} null, lef[maxn], rig[maxn], val[13][maxm];inline linear_base operator + (linear_base A, const linear_base &B) { for (int i = 19; ~i; --i) { if (B.a[i]) A.ins(B.a[i], i); } return A;}const int maxn_r = maxn * 23, maxn_w = maxn * 8;char buf_r[maxn_r], *now_r = buf_r;char buf_w[maxn_w], *now_w = buf_w;inline int read() { int x = 0; while (*now_r < 48) ++now_r; while (*now_r > 47) x = (x << 3) + (x << 1) + (*now_r ^ 48), ++now_r; return x;}inline void write(int x) { static char *tp, st[7]; if (!x) *now_w = 48, ++now_w; for (tp = st; x; *++tp = x % 10 | 48, x /= 10); while (tp != st) *now_w = *tp, ++now_w, --tp; *now_w = 10, ++now_w;}inline linear_base query(const int &l, const int &r) { if (l > r) return null; const int k = lg[r - l + 1]; return val[k][l] + val[k][r - (1 << k) + 1];}int main() { fread(buf_r, 1, maxn_r, stdin); n = read(), tot = get(n); for (int i = 1; i <= n; ++i) { a[i] = read(); val[0][get(i)].ins(a[i]); } for (int i = 2; i <= tot; ++i) { lg[i] = lg[i >> 1] + 1; } linear_base lst; lst.clr(); for (int i = 1; i <= n; ++i) { lst.ins(a[i]), lef[i] = lst; if (!(i & base)) lst.clr(); } lst.clr(); for (int i = n; i; --i) { if (!(i & base)) lst.clr(); lst.ins(a[i]), rig[i] = lst; } for (int i = 1; i <= lg[tot]; ++i) { for (int j = 1; j + (1 << i) - 1 <= tot; ++j) { val[i][j] = val[i - 1][j] + val[i - 1][j + (1 << (i - 1))]; } } m = read(); register linear_base ans; for (int q = 1; q <= m; ++q) { const int l = read(), r = read(); const int L = get(l), R = get(r); ans.clr(); if (L == R) { for (register int i = l; i <= r; ++i) { ans.ins(a[i]); } } else { ans = rig[l] + lef[r] + query(L + 1, R - 1); } write(ans.query()); } fwrite(buf_w, 1, now_w - buf_w, stdout); return 0;}