[bzoj 4184] shallot

n 个操作: 加入 / 删除一个数. 每次操作后, 求当前数的最大异或和. (n ≤ 5*10^5, 数 < 2^31) 用等价于高斯消元的方法, 往集合里动态加数, 同时维护线性基, 可以单次 O(lg X). 但是, 像并查集一样, 要删掉一个数就不那么容易了.

[bzoj 4025] 二分图

不强制在线, 不妨对时间分治. 把一个数存在的时间分解成 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;
}