Description

【题意】
给出$n$ 个数 $a_i$，有$q$个询问，每个询问 $[l,r]$ 求：在$a_l \dots a_r $中选取任意个，使得它们的异或和最大。

【输入格式】
第一行一个整数 $ n $ ( $ 1 \leq n \leq 500\,000 $ ) 。
下来$ n $ 个整数 $ a_i $,( $ 0 \leq a_i \leq 10^6 $ )。
下来一个整数 $ q $ ( $ 1 \leq q \leq 500\,000 $ ) 。
下来$ q $ 行，每行两个整数 $ l_i $ 和 $ r_i $ ( $ 1 \leq l_i \leq r_i \leq n $ ) 。

【输出格式】
每个询问输出一行一个结果。

【样例输入 #1】
4
7 2 3 4
3
1 4
2 3
1 3

【样例输出 #1】
7
3
7

【样例输入 #2】
5
12 14 23 13 7
15
1 1
1 2
1 3
1 4
1 5
2 2
2 3
2 4
2 5
3 3
3 4
3 5
4 4
4 5
5 5

【样例输出 #2】
12
14
27
27
31
14
25
26
30
23
26
29
13
13
7

Hint

G69 前缀线性基+贪心法 CF1100F Ivan and Burgers

#pragma optimize(2)
#include<bits/stdc++.h>
using namespace std;typedef long long LL;
const int N=5e5+10,B=30;
template<typename T>void qr(T &x)
{
	x=0;char c=getchar();
	for(;!isdigit(c);c=getchar());
	for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c&15);
}
template<typename T>void qw(T x)
{
	if(x>=10)qw(x/10);
	putchar(x%10+'0');
}
int a[N], bas[N][B+1];int pos[N][B+1];
void ins(int x,int bass[],int poss[])
{
int v=a[x];
for(int i=B;i>=0;i--)if((v>>i)&1)
{
if(!bass[i]){bass[i]=v,poss[i]=x;return ;}
if(poss[i]<x){swap(x,poss[i]);swap(v,bass[i]);}
v^=bass[i];
}
}
int main()
{
int n;qr(n);
memset(bas[0],0,sizeof(bas[0]));memset(pos[0],0,sizeof(pos[0]));
for(int i=1;i<=n;i++)
{
qr(a[i]);
memcpy(bas[i],bas[i-1],sizeof(bas[i]));
memcpy(pos[i],pos[i-1],sizeof(pos[i]));
ins(i,bas[i],pos[i]);
}
int q,l,r;qr(q);
while(q--)
{
qr(l);qr(r);
int ans=0;
for(int i=B;i>=0;i--)if(pos[r][i]>=l)ans=max(ans,ans^bas[r][i]);
qw(ans);
putchar('\n');
}
return 0;
}

</p>