Description：

求区间异或最大值。

$1\leqslant n\leqslant 5\times 10^5$

Solution：

把询问离线按右端点排序，然后每次插入一个数，在线性基中记一下每个位置上的数在原数列的什么位置，然后如果线性基某一位是零，那么直接把这个数插进去即可，否则在那个位置保留一个位置比较靠后的，然后把另一个继续向下传递，这样线性基中的每一位都是尽量靠右的，那么我们每次询问只使用 $pos\geqslant l$ 的就可以了。

Code：

#include<bits/stdc++.h>

using namespace std;

int n,m;

#define MAXN 500010

int a[MAXN];

struct LB

{

	int d[31];

	int pos[31];

	void insert(int p,int x)

	{

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

		{

			if(x & (1 << i))

			{

				if(d[i] == 0)

				{

					d[i] = x;

					pos[i] = p;

					break;

				}

				else

				{

					if(p > pos[i])

					{

						swap(x,d[i]);

						swap(p,pos[i]);

					}

					x ^= d[i];

				}

			}

		}

		return;

	}

	int query(int l)

	{

		int res = 0;

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

		{

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

		}

		return res;

	}

}s;

struct query

{

	int l,r,ans,id;

}q[MAXN];

bool cmp_r(query a,query b){return a.r < b.r;}

bool cmp_id(query a,query b){return a.id < b.id;}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	scanf("%d",&m);

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

	{

		scanf("%d%d",&q[i].l,&q[i].r);

		q[i].id = i;

	}

	sort(q + 1,q + 1 + m,cmp_r);

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

	{

		s.insert(r,a[r]);

		while(i <= m && q[i].r == r)

		{

			q[i].ans = s.query(q[i].l);

			++i;

		}

	}

	sort(q + 1,q + 1 + m,cmp_id);

	for(int i = 1;i <= m;++i)printf("%d\n",q[i].ans);

	return 0;

}