题意：给定n个数，每个数为c[i]，有q个询问，每次询问从第l个到第r个数字的最大xor和
n,q<=5e5，c[i]<=1e6，时限3s
思路：直接线段树维护区间线性基是3个log，会T
做法1：因为不是强制在线把询问分治能降到2个log
#include<bits/stdc++.h>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef set<int>::iterator iter;
#define fi first
#define se second
#define MP make_pair
#define mem0(a) memset(a,0,sizeof(a))
#define N 510000
#define M 15
#define MOD 1000000007
#define eps 1e-10
#define pi acos(-1)
#define oo 1e9
int read()
{
int v=,f=;
char c=getchar();
while(c<||<c) {if(c=='-') f=-; c=getchar();}
while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();
return v*f;
}
struct base
{
//ll d[20],p[20];
int d[];
int cnt; base()
{
memset(d,,sizeof(d));
//memset(p,0,sizeof(p));
cnt=;
}
bool insert(int val)
{
if(val==) return ;
for(int i=;i>=;i--)
if((val>>i)&)
{
if(!d[i])
{
d[i]=val;
break;
}
val^=d[i];
}
return val>;
}
int query_max()
{
int ret=;
for(int i=;i>=;i--) ret=max(ret,ret^d[i]);
return ret;
}
int query_min()
{
for(int i=;i<=;i++)
if(d[i]) return d[i];
return ;
}
/*void rebuild()
{
for(int i=20;i>=0;i--)
for(int j=i-1;j>=0;j--)
if((d[i]>>j)&1) d[i]^=d[j];
for(int i=0;i<=20;i++)
if(d[i]) p[cnt++]=d[i];
}
ll kthquery(ll k)
{
int ret=0;
if(k>=(1LL<<cnt)) return -1;
for(int i=20;i>=0;i--)
if((k>>i)&1) ret^=p[i];
return ret;
}*/ base operator+(const base&_A)const
{
base ret=*this;
for(int i=;i>=;i--)
if(_A.d[i]) ret.insert(_A.d[i]);
return ret;
}
}t[N],b;
struct arr
{
int x,y,id;
}q[N],c[N];
int a[N],ans[N]; /*base merge(const base &n1,const base &n2)
{
base ret=n1;
for(int i=20;i>=0;i--)
if(n2.d[i]) ret.insert(n1.d[i]);
return ret;
}*/
void solve(int l,int r,int x,int y)
{
if(l==r)
{
for(int i=x;i<=y;i++) ans[q[i].id]=a[l];
return;
}
if(x>y) return;
int mid=(l+r)>>;
memset(b.d,,sizeof(b.d));
for(int i=mid;i>=l;i--)
{
b.insert(a[i]);
for(int j=;j<=;j++) t[i].d[j]=b.d[j];
}
memset(b.d,,sizeof(b.d));
for(int i=mid+;i<=r;i++)
{
b.insert(a[i]);
for(int j=;j<=;j++) t[i].d[j]=b.d[j];
}
int l1=x,r1=y;
for(int i=x;i<=y;i++)
{
if(q[i].y<=mid) c[l1++]=q[i];
else if(q[i].x>mid) c[r1--]=q[i];
else
{
base tmp=t[q[i].x]+t[q[i].y];
ans[q[i].id]=tmp.query_max();
}
}
for(int i=x;i<l1;i++) q[i]=c[i];
for(int i=r1+;i<=y;i++) q[i]=c[i];
solve(l,mid,x,l1-);
solve(mid+,r,r1+,y);
}
int main()
{
//freopen("cf1100f.in","r",stdin);
//freopen("cf1100f.out","w",stdout);
int n,m;
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
scanf("%d",&m);
for(int i=;i<=m;i++)
{
scanf("%d%d",&q[i].x,&q[i].y);
q[i].id=i;
}
solve(,n,,m);
for(int i=;i<=m;i++) printf("%d\n",ans[i]);
return ;
}
做法2：假设固定右端点，维护log个维上使生成空间变大的最大的l
比做法1快3倍
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> Pll;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef pair<ll,int>P;
#define N 510000
#define M 151000
#define fi first
#define se second
#define MP make_pair
#define pi acos(-1)
#define mem(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++)
#define per(i,a,b) for(int i=(int)a;i>=(int)b;i--)
#define lowbit(x) x&(-x)
#define Rand (rand()*(1<<16)+rand())
#define id(x) ((x)<=B?(x):m-n/(x)+1)
#define ls p<<1
#define rs p<<1|1
const ll MOD=1e9+,inv2=(MOD+)/;
double eps=1e-;
ll INF=1e18;
ll inf=5e13;
int dx[]={-,,,};
int dy[]={,,-,};
int f[N][],g[N][],a[N];
int read()
{
int v=,f=;
char c=getchar();
while(c<||<c) {if(c=='-') f=-; c=getchar();}
while(<=c&&c<=) v=(v<<)+v+v+c-,c=getchar();
return v*f;
}
void add(int i,int x)
{
int k=i;
per(j,,) f[i][j]=f[i-][j],g[i][j]=g[i-][j];
per(j,,)
if(x>>j)
{
if(!f[i][j])
{
f[i][j]=x;
g[i][j]=k;
break;
}
else
{
if(k>g[i][j])
{
swap(k,g[i][j]);
swap(x,f[i][j]);
}
x^=f[i][j];
}
}
}
int main()
{
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
//int cas=read();
//while(cas--)
//{
int n=read();
rep(i,,n)
rep(j,,) f[i][j]=g[i][j]=;
int lastans=;
rep(i,,n)
{
a[i]=read();
add(i,a[i]);
}
int m=read();
while(m--)
{
int l=read(),r=read();
lastans=;
per(i,,)
if((lastans^f[r][i])>lastans&&g[r][i]>=l) lastans^=f[r][i];
printf("%d\n",lastans);
}
//}
return ;
}