Codeforces：1100F-F. Ivan and Burgers（离线线性基）

题目链：http://codeforces.com/problemset/problem/1100/F

题意：现在有n个数，q次询问，每次询问给你一段区间，然后你需要在区间中选出一些数要这些数的异或和最大。

解题心得：

• 选数然后异或和最大以看就知道是线性基。
• 但是这个题限定了区间，如果每次询问建立新的线性基肯定TLE。所以这个题需要离线处理，首先将所有的询问按照右端点排序，然后将数插入线性基，在插入的同时要记录数值和数的位置，如果当前位已经有了数值，并且这个数位置在现在这个数的前面，则用现在这个数将记录的数替换出来，然后继续往下插入替换出来的数。也就是越后面的数要尽量的往二进制位大的方向放。最后查询时只有记录下来的数位置在查询区间中的才参与答案的改变。这样就可以一边插入数值一边得到答案。

---

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn = 5e5+100;
    int n, m, num[maxn], ans[maxn];
     
    struct Cxx {
        int va, pos;
    }cxx[maxn];
     
    struct Query {
        int l, r, pos;
        bool operator < (const Query &x) const {
            if(r == x.r) return x.l > l;
            else return x.r > r;
        }
    }query[maxn];
     
    void init() {
        scanf("%d", &n);
        for(int i=1;i<=n;i++) {
            scanf("%d", &num[i]);
        }
        scanf("%d", &m);
        for(int i=1;i<=m;i++) {
            scanf("%d%d",&query[i].l, &query[i].r);
            query[i].pos = i;
        }
        sort(query+1, query+1+m);
    }
     
    void insert(int va, int pos) {
        for(int i=30;i>=0;i--) {
            if(va&(1<<i)) {
                if(cxx[i].va == 0) {
                    cxx[i].va = va;
                    cxx[i].pos = pos;
                    break;
                } else if(pos > cxx[i].pos){
                    Cxx temp = cxx[i];
                    cxx[i].pos = pos;
                    cxx[i].va = va;
                    pos = temp.pos;
                    va = temp.va;
                }
                va ^= cxx[i].va;
            }
        }
    }
     
    int get_ans(int pos) {
        int l = query[pos].l;
        int r = query[pos].r;
     
        int sum = 0;
        for(int i=30;i>=0;i--) {
            if(cxx[i].pos >= l && cxx[i].pos <= r) {
                sum = max(sum, sum^cxx[i].va);
            }
        }
        return sum;
    }
     
    int main() {
    //    freopen("1.in.txt", "r", stdin);
        init();
        int pos = 1;
        for(int i=1;i<=n;i++) {
            insert(num[i], i);
            while(i == query[pos].r) {
                ans[query[pos].pos] = get_ans(pos);
                pos++;
            }
        }
     
        for(int i=1;i<=m;i++) {
            printf("%d\n", ans[i]);
        }
        return 0;
    }