给定一个长度为 $n$ 的序列 $a$，$q$ 次询问 $[l,r]$ 内选数的最大异或和。
$n, q \leq 5 \times 10^5, a_i \leq 10^6$。
3s，512 MB

很简单啊，直接 RMQ 就做完了。
然后太冲动了直接 Coding 所导致的忘记算空间了。
ST 表再内套一个线性基直接 $O(n \log n \log V)$，空间复杂度起飞了，算了下大概 700 多 MB 的样子。
于是交上去喜提 MLE On Test #1，老实了。

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;

int n, m, a[N], lg[N];

inline bool chk(int x, int i) { return (x >> i) & 1; }
struct BIT {
    int base[22];
    inline void insert(int x) {
        if (!x) return;
        for (int i = 20; i >= 0; i--) {
            if (!chk(x, i)) continue;
            if (!base[i]) return base[i] = x, void();
            x ^= base[i];
        }
    }
    inline int query() {
        int res = 0;
        for (int i = 20; i >= 0; i--) res = max(res, res ^ base[i]);
        return res;
    }
} bit[N][20];

inline BIT merge(BIT a, BIT b) {
    for (int i = 20; i >= 0; i--) a.insert(b.base[i]);
    return a;
}

void init() {
    for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= n; i++) bit[i][0].insert(a[i]);
    for (int i = 1; i <= 19; i++)
        for (int j = 1; j + (1 << i) - 1 <= n; j++)
            bit[j][i] = merge(bit[j][i - 1], bit[j + (1 << i - 1)][i - 1]);
}

int query(int l, int r) {
    int len = lg[r - l + 1];
    return merge(bit[l][len], bit[r - (1 << len) + 1][len]).query();
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    init();
    scanf("%d", &m);
    while (m--) {
        int l, r; scanf("%d%d", &l, &r);
        printf("%d\n", query(l, r) );
    }
    return 0;
}

正解完全没有半点头绪，于是开始卡空间，然后发现这玩意儿不能开 short……
但是注意到如果可以时间换空间那就很强了，因为 $5 \times 10^8$ 空间开不下但可以跑得过。
去问了一下，发现原来是我没学过猫树分治 (lll￢ω￢)。

可能和网上的版本有些差别？因为没有仔细学，了解思想之后直接现推了。
ST 表能解决的问题猫树都能解决，不同于 ST 表的倍增，猫树的基本思想是分治，大致可以理解为是 ST 表和线段树的结合。
由于结合了 ST 表，它一般不支持修改操作，但可以通过离线等方式快速处理询问，再拼接成答案。

具体地，它的分治树长得和线段树几乎一样，对于一次询问 $[l,r]$，我们需要寻找一个树上区间 $[L,R]$，使得 $L \leq l \leq mid \lt mid + 1 \leq r \leq R$。
然后对于树上的每个区间 $[L,R]$，考虑记录它的前后缀答案，对于一次询问只需要合并 $[L,mid]$ 和 $[mid+1,R]$ 两个区间的后缀、前缀答案。

对于这题，考虑把问题离线下来，先找到 $[l,r]$ 对应的 $[L,R]$ 把询问插入这个区间，然后对每一个区间计算前后缀的线性基。
由于猫树深度是 $O(\log n)$ 的，所以这样做的复杂度是 $O(n \log n \log V)$，$\log V$ 是线性基插入元素复杂度。
查询可以直接合并两个线性基，做到 $O(\log^2 V)$。

感觉写的会非常抽象……因为没有看过猫树的正统写法，随手胡的代码。

事实上并不抽象，甚至几乎一遍过。

#include <bits/stdc++.h>
#define PII pair<int, int>
using namespace std;
const int N = 5e5 + 5;

int n, m, a[N];

inline bool chk(int x, int i) { return (x >> i) & 1; }
struct BIT {
    int base[22];
    inline void clr() { for (int i = 20; i >= 0; i--) base[i] = 0; }
    inline void insert(int x) {
        if (!x) return;
        for (int i = 20; i >= 0; i--) {
            if (!chk(x, i)) continue;
            if (!base[i]) return base[i] = x, void();
            x ^= base[i];
        }
    }
    inline int query() {
        int res = 0;
        for (int i = 20; i >= 0; i--) res = max(res, res ^ base[i]);
        return res;
    }
} la[N], ra[N];
inline int merge(BIT a, BIT b) {
    for (int i = 20; i >= 0; i--) a.insert(b.base[i]);
    return a.query();
}

vector< PII > pre[N << 2], suf[N << 2];
inline bool cmp(PII a, PII b) { return a > b; }

void insert(int u, int l, int r, int ql, int qr, int id) {
    if (l == r) return suf[u].push_back({l, id}), pre[u].push_back({r, id}), void();
    int mid = l + r >> 1;
    if (l <= ql && ql <= mid && mid + 1 <= qr && qr <= r) return suf[u << 1].push_back({ql, id}), pre[u << 1 | 1].push_back({qr, id}), void();
    if (qr <= mid) insert(u << 1, l, mid, ql, qr, id);
    else insert(u << 1 | 1, mid + 1, r, ql, qr, id);
}

void solve(int u, int l, int r) {
    int mid = l + r >> 1, now = 0; BIT t;

    sort(pre[u].begin(), pre[u].end());
    now = l, t.clr();
    for (PII it : pre[u]) {
        while (now <= it.first) t.insert(a[now++]);
        ra[it.second] = t;
    }

    sort(suf[u].begin(), suf[u].end(), cmp);
    now = r, t.clr();
    for (PII it : suf[u]) {
        while (now >= it.first) t.insert(a[now--]);
        la[it.second] = t;
    }

    if (l == r) return;
    solve(u << 1, l, mid), solve(u << 1 | 1, mid + 1, r);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    scanf("%d", &m);
    for (int i = 1, l, r; i <= m; i++) scanf("%d%d", &l, &r), insert(1, 1, n, l, r, i);
    solve(1, 1, n);

    for (int i = 1; i <= m; i++) printf("%d\n", merge(la[i], ra[i]) );
    return 0;
}