线性基

struct XorBasis
{
    typedef ll type;

    vector<type>G;
    bool zero;

    XorBasis() {clear();}

    void insert(type x)
    {
        for(int i=sz(G)-1;~i && x;--i)
        {
            type t=x^G[i];
            if(t<x)
            {
                if(t>G[i])break;
                x^=G[i];
            }
        }
        if(!x){zero=true;return;}
        G.pb(x);
        for(int i=sz(G)-1;i && G[i]<G[i-1];--i)
            swap(G[i],G[i-1]);
    }

    void build()
    {
        for(int i=0;i<sz(G);++i)
            for(int j=i+1;j<sz(G);++j)
                if((G[j]^G[i])<G[j])
                    G[j]^=G[i];
    }

    type get_max()
    {
        type res=0;
        for(int i=sz(G)-1;i>=0;--i)
            if((res^G[i])>res)
                res^=G[i];
        return res;
    }

    type kth(ll k)
    {
        if(zero && !--k)return 0;
        if(k>=(1ll<<sz(G)))return -1;
        type ans=0;
        for(int i=sz(G)-1;i>=0;--i)
        {
            type x=(1ll<<i);
            if(k>=x)k-=x,ans^=G[i];
            if(!k)return ans;
        }
        return ans;
    }

    int size() {return G.size()+zero;}

    void clear()
    {
        zero=false;
        G.clear();
    }
}X;

可持久化线性基

struct PersistentXorBasis
{
    static const int __=5e5+5;
    typedef int type;

    struct XorBasis
    {
        vector<pair<type,int> >G;
        int zero;   //最后出现的位置

        XorBasis() {clear();}

        void operator=(const XorBasis &b)
        {
            for(int i=0;i<sz(b.G);++i)
                G.push_back(b.G[i]);
            zero=b.zero;
        }

        int size() {return G.size()+bool(zero);}

        void clear()
        {
            zero=0;
            G.clear();
        }
    }X[__];

    int n;

    void insert(pair<type,int>x)
    {
        vector<pair<type,int> >&G=X[x.se].G;
        for(int i=sz(G)-1;~i && x.fi;--i)
        {
            type t=x.fi^G[i].fi;
            if(t<x.fi)
            {
                if(t>G[i].fi)break;
                if(x.se>G[i].se)swap(G[i],x);
                x.fi^=G[i].fi;
            }
        }
        if(!x.fi){X[x.se].zero=x.se;return;}
        G.pb(x);
        for(int i=sz(G)-1;i && G[i].fi<G[i-1].fi;--i)
            swap(G[i],G[i-1]);
    }

    void build(type a[],int _n)
    {
        n=_n;
        for(int i=1;i<=n;++i)
        {
            X[i]=X[i-1];
            insert(make_pair(a[i],i));
        }
    }

    type get_max(int l,int r)
    {
        vector<pair<type,int> >&G=X[r].G;

        type res=0;
        for(int i=sz(G)-1;~i;--i)
            if(G[i].se>=l && (res^G[i].fi)>res)
                res^=G[i].fi;
        return res;
    }

    void clear()
    {
        for(int i=1;i<=n;++i)
            X[i].clear();
    }
}X;