hdu 6579（在线线性基模板）

题意： 在线查询某一个区间内的 异或最大值。

思路：我们对于序列中的每一个点，考虑以这个点为右端点向左进行扩展。记录线性基每一次扩展的位置。

           我们考虑通过递推来维护线性基，当从 r 递推到 r + 1时。考虑 第一个 与 a[ r ] 相交的基向量。我们考虑将这一个基向量X替换为 a[ r ] 。这样，然后我们将  X 替换为 X ^ a[ r ] 并将这个向量继续向后插入，显然与直接将X向后插入是等价的。如果后面的基向量的出现位置在X的前面，那么我们同上将 这个向量替换为 X。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int base = 30;
const int maxn = 500005;
template <typename T>
struct node
{
    T a[base+1];        //线性基的插入结果
    int pos[base+1];
    void init(){
        memset( a,0,sizeof(a) );
        memset( pos,0,sizeof(pos) );
    }
    bool ins(T b,int _pos)         // 向线性基中插入一个数
    {
        for(int i=base;i>=0;i--)
            if(b>>i){
                int tmp = a[i];
                if(!a[i])
                {
                    a[i]=b;pos[i] = _pos;
                    return true ;
                }else{
                    if( pos[i] < _pos ){
                        tmp = a[i];
                        a[i] = b;
                        swap( pos[i],_pos );
                    }
                }
                b^=tmp;
            }
        return false ;
    }
    bool check (T b)        // 如果可以表示出来，返回true ，否则返回 false
    {
        for(int i=base;i>=0;i--)
        {
            if(b>>i)
            {
                if(!a[i])return false ;
                b^=a[i];
            }
        }
        return true ;
    }
    T solve( int l ){           //在线线性基区间查询操作，左端点为l
        int res = 0;
        for( int i = base;i >= 0;i-- ){
            if( a[i] && pos[i] >= l && !(res >> i & 1) ){
                res ^= a[i];
            }
        }
        return res;
    }
};
node<int>t[1000005];
int a[maxn];
void append( int id,int v ){     // 向当前序列的结尾插入一个数
    t[id] = t[id-1];
    t[id].ins( v,id );
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        t[0].init();
        int lastans = 0,n,m;
        scanf("%d%d",&n,&m);
        for( int i = 1;i <= n;i++ ){
            scanf("%d",&a[i]);
            append( i,a[i] );
        }
        for( int i = 1;i <= m;i++ ){
            int op,l,r;scanf("%d",&op);
            if( op==0 ){
                scanf("%d%d",&l,&r);
                l = (l ^lastans)%n+1; r = (r^lastans)%n+1;
                if( l > r ) swap( l,r );
                lastans = t[r].solve( l );
                printf("%d\n",lastans);
            }else{
                int x;
                scanf("%d",&x);
                x ^= lastans;
                append(++n,x);
            }
        }
    }
    return 0;
}