【题解】shallot 线性基+时域线段树 BZOJ4184 ——quhengyi11

传送门

一道套路题

首先这个全局异或值最大的信息显然可以用线性基来维护

但是线性基不滋磁删除怎么办啊？

以时间建立线段树，算出每个数出现的时间区间，并在线段树的每个节点存个 $vector$来记录所有向量，然后每次询问就跑到线段树的叶子节点，然后合并路径上的向量即可。这样就避免了删除操作。

还有一个 $trick$就是你现在维护的线性基不一定是要按照原本线性基的写法，对角矩阵有 $1$的位置，它上面必须全是 $0$，这样写是为了方便维护线性基内值域的 $rank$的，我们这里不需要维护 $rank$也就不需要这样处理，直接在询问的时候从大到小枚举判断是否能优化 $ans$即可

#include<bits/stdc++.h>
#define Re register
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define eps 1e-4
#define mod 10086
#define lowbit(x) (x & -x)
#define N 500005
#define ls (u << 1)
#define rs (u << 1 | 1)
#define cl(arr) memset(arr, 0, sizeof arr)
inline void read (int &x)
{
    x = 0;
    Re char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = (x << 3) + (x << 1) + ch - '0', ch = getchar();
}
int n, base = 31, cnt, tot, k;
std::vector<int> t[N << 2];
struct node {
    int b[32];
} qwq;
inline void ins (node &b, int x)
{
    fd (j, base, 0)
        if (x >> j & 1)
        {
            if (b.b[j]) x ^= b.b[j];
            else
            {
                b.b[j] = x;
                break;
            }
        }
}
int a[N];
std::map<int, int> ri;
inline void update (int u, int L, int R, int l, int r, int v)
{
    if (l <= L && R <= r) { t[u].pb(v); return; }
    int mid = L + R >> 1;
    if (l <= mid) update (ls, L, mid, l, r, v);
    if (mid < r) update(rs, mid + 1, R, l, r, v);
}
inline void query (int u, int L, int R, node b)
{
    int sz = t[u].size() - 1;
    fo (i, 0, sz) ins(b, t[u][i]);
    if (L == R)
    {
        int ans = 0;
        fd (i, base, 0) 
            if ((b.b[i] ^ ans) > ans) ans = b.b[i] ^ ans;
        printf("%d\n", ans);
        return;
    }
    int mid = L + R >> 1;
    query(ls, L, mid, b); query(rs, mid + 1, R, b);
}
int main ()
{
    read(n);
    fo (i, 1, n) 
    {
        scanf("%d", &a[i]);
        if (a[i] < 0) ri[-a[i]] = i;
    }
    fo (i, 1, n)
        if (a[i] > 0)
        {
            if (ri.find(a[i]) != ri.end())
                update(1, 1, n, i, ri[a[i]] - 1, a[i]);
            else
                update(1, 1, n, i, n, a[i]);
        }
    query(1, 1, n, qwq);
    return 0;
}