Description：

$n$ 个时间点每个时间点可以插入或删除一个数，问每个时刻最大异或值。

$1\le N \le 500000$

Solution：

异或最大值用线性基，线性基不支持删除，于是在线段树上对时间分治，每个节点存一个 $vector$ ，将一个数的插入和删除看作在线段树上的一段区间打标记，用标记永久化的思想带着一个 $LinearBase$ 在线段树上 $dfs$ ，到一个节点时将 $vector$ 中的数插进去，到叶子结点时计算答案即可。

处理用 $map$

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<map>

#include<vector>

#include<cstring>

using namespace std;

int n;

const int BASE = 30;

struct base

{

	int d[33];

	void init()

	{

		memset(d,0,sizeof(d));

		return;

	}

	void insert(int k)

	{

		for(int i = BASE;i >= 0;--i)

		{

			if(k & (1 << i))

			{

				if(d[i] == 0)

				{

					d[i] = k;

					break;

				}

				else

				{

					k ^= d[i];

				}

			}

		}

		return;

	}

	int query()

	{

		int res = 0;

		for(int i = BASE;i >= 0;--i)

		{

			if((res ^ d[i]) > res)res ^= d[i];

		}

		return res;

	}

}set;

#define MAXN 500010

int a[MAXN];

map<int,int> cnt;

map<int,int> st;

bool cmp(int x,int y){return abs(a[x]) < abs(a[y]);}

struct node

{

	vector<int> v;

	int lc,rc;

	node(){v.clear();lc = rc = 0;}

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	int mid = ((l + r) >> 1);

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void add(int rt,int L,int R,int k,int l,int r)

{

	if(L <= l && r <= R)

	{

		t[rt].v.push_back(k);

		return;

	}

	int mid = ((l + r) >> 1);

	if(L <= mid)add(t[rt].lc,L,R,k,l,mid);

	if(R >= mid + 1)add(t[rt].rc,L,R,k,mid + 1,r);

	return;

}

void pt(int rt,int l,int r,base s)

{

	for(int i = 0;i < t[rt].v.size();++i)s.insert(t[rt].v[i]);

	if(l == r)

	{

		printf("%d\n",s.query());

		return;

	}

	int mid = ((l + r) >> 1);

	pt(t[rt].lc,l,mid,s);

	pt(t[rt].rc,mid + 1,r,s);

	return;

}

int main()

{

	scanf("%d",&n);

	build(root,1,n);

	for(int i = 1;i <= n;++i)

	{

		scanf("%d",&a[i]);

	}

	for(int i = 1;i <= n;++i)

	{

		if(a[i] > 0)

		{

			if(cnt[a[i]] == 0)

			{

				st[a[i]] = i;

			}

			++cnt[a[i]];

		}

		else

		{

			if(cnt[-a[i]] > 1)

			{

				--cnt[-a[i]];

			}

			else

			{

				--cnt[-a[i]];

				add(root,st[-a[i]],i - 1,-a[i],1,n);

			}

		}

	}

	for(int i = 1;i <= n;++i)

	{

		if(cnt[a[i]] > 0)

		{

			add(root,st[a[i]],n,a[i],1,n);

			cnt[a[i]] = 0;

		}

	}

	base s;

	s.init();

	pt(root,1,n,s);

	return 0;

}