关于一种快速区间线性基

· · 个人记录

关于一种快速离线区间线性基

考虑在记录基底是啥的基础上，记录它是由哪个位置上的元素加进来的。然后我们把询问按照右端点从小到大排序，处理询问时，我们把加入位置在当前左端点左边的基底排除掉即可。

注意到，如果是这样的话，我们的线性基应该是从右往左加的，因为要优先用右边的。但实际上我们做的时候是从左往右加的，我们来考虑怎么修改插入能满足要求。

考虑插入线性基时考虑每一位的过程，因为我们当前这个是最先加的，所以碰到最高位直接就加入线性基。但问题是原来这这里面的基底怎么办呢，重新插入一遍就好了，并维护好时间戳。但此时我们这个并不是最新的，所以碰到比它更新的就不要加了，异或上就行。

看代码可能更清楚。

void insert(int x, int tim)
{
    for (int i = LN - 1; ~i; --i)
    {
        if (!(x & (1 << i))) continue;
        if (!c[i]) { c[i] = x; tag[i] = tim; break; }
        int t = c[i];
        if (tag[i] < tim) std::swap(tim, tag[i]), c[i] = x; 
        x ^= t;
    }
}

int nowR = 0;
for (int i = 1; i <= tn; ++i)
{
    while (nowR < q[i].r) ++nowR, now.insert(a[rev[nowR]], nowR);   
    for (int j = 0; j < LN; ++j)
        if (now.tag[j] >= q[i].l)
            ret[q[i].t][q[i].id].insert(now.c[j], 0);
}

在线也很简单，你暴力记录 n 个版本就行了。