n 个操作: 加入 / 删除一个数. 每次操作后, 求当前数的最大异或和. (n ≤ 5*10^5, 数 < 2^31) 用等价于高斯消元的方法, 往集合里动态加数, 同时维护线性基, 可以单次 O(lg X). 但是, 像并查集一样, 要删掉一个数就不那么容易了.
不强制在线, 不妨对时间分治. 把一个数存在的时间分解成 O(lg n) 个区间, 遍历线段树, 在叶子节点进行查询.
const int N = 5e5;
struct LinearBasis
{
vector<int> x;
void insert(int v)
{
rep (i, 0, x.size())
if ((v ^ x[i]) < v) v ^= x[i];
if (v)
{
rep (i, 0, x.size())
if ((x[i] ^ v) < x[i]) x[i] ^= v;
x.push_back(v);
}
}
int ask()
{
int v = 0;
rep (i, 0, x.size()) v ^= x[i];
return v;
}
} B;
struct Num
{
int l, r, v;
} S[N];
int ans[N];
map<int, int> t, cnt;
void solve(int l, int r, Num* x, Num* y, LinearBasis B)
{
int m = (l+r)/2;
Num* p, * q;
for (p = x; p != y; ++p)
if (p->l <= l && p->r >= r)
B.insert(p->v), swap(*p, *x++);
if (l == r)
{
ans[l] = B.ask();
return;
}
for (p = q = x; p != y; ++p)
if (p->l <= m) swap(*p, *q++);
solve(l, m, x, q, B);
for (p = q = x; p != y; ++p)
if (p->r > m) swap(*p, *q++);
solve(m+1, r, x, q, B);
}
int main()
{
int n, m = 0, v;
scanf("%d", &n);
rep (i, 0, n)
{
scanf("%d", &v);
if (v > 0)
{
if (++cnt[v] == 1)
S[t[v] = m++] = (Num){i, n-1, v};
}
else
{
if (cnt[-v]-- == 1)
S[t[-v]].r = i-1;
}
}
solve(0, n-1, S, S+m, B);
rep (i, 0, n)
printf("%d\n", ans[i]);
return 0;
}