题意：给定n个数，每个数为c[i]，有q个询问，每次询问从第l个到第r个数字的最大xor和
n,q<=5e5，c[i]<=1e6，时限3s
思路：直接线段树维护区间线性基是3个log，会T
做法1：因为不是强制在线把询问分治能降到2个log
1 #include<bits/stdc++.h> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<cmath> 6 #include<iostream> 7 #include<algorithm> 8 #include<map> 9 #include<set> 10 #include<queue> 11 #include<vector> 12 #include<bitset> 13 using namespace std; 14 typedef long long ll; 15 typedef unsigned int uint; 16 typedef unsigned long long ull; 17 typedef pair<int,int> PII; 18 typedef vector<int> VI; 19 typedef set<int>::iterator iter; 20 #define fi first 21 #define se second 22 #define MP make_pair 23 #define mem0(a) memset(a,0,sizeof(a)) 24 #define N 510000 25 #define M 15 26 #define MOD 1000000007 27 #define eps 1e-10 28 #define pi acos(-1) 29 #define oo 1e9 30 31 int read() 32 { 33 int v=0,f=1; 34 char c=getchar(); 35 while(c<48||57<c) {if(c=='-') f=-1; c=getchar();} 36 while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar(); 37 return v*f; 38 } 39 40 struct base 41 { 42 //ll d[20],p[20]; 43 int d[20]; 44 int cnt; 45 46 base() 47 { 48 memset(d,0,sizeof(d)); 49 //memset(p,0,sizeof(p)); 50 cnt=0; 51 } 52 bool insert(int val) 53 { 54 if(val==0) return 0; 55 for(int i=20;i>=0;i--) 56 if((val>>i)&1) 57 { 58 if(!d[i]) 59 { 60 d[i]=val; 61 break; 62 } 63 val^=d[i]; 64 } 65 return val>0; 66 } 67 int query_max() 68 { 69 int ret=0; 70 for(int i=20;i>=0;i--) ret=max(ret,ret^d[i]); 71 return ret; 72 } 73 int query_min() 74 { 75 for(int i=0;i<=20;i++) 76 if(d[i]) return d[i]; 77 return 0; 78 } 79 /*void rebuild() 80 { 81 for(int i=20;i>=0;i--) 82 for(int j=i-1;j>=0;j--) 83 if((d[i]>>j)&1) d[i]^=d[j]; 84 for(int i=0;i<=20;i++) 85 if(d[i]) p[cnt++]=d[i]; 86 } 87 ll kthquery(ll k) 88 { 89 int ret=0; 90 if(k>=(1LL<<cnt)) return -1; 91 for(int i=20;i>=0;i--) 92 if((k>>i)&1) ret^=p[i]; 93 return ret; 94 }*/ 95 96 base operator+(const base&_A)const 97 { 98 base ret=*this; 99 for(int i=20;i>=0;i--) 100 if(_A.d[i]) ret.insert(_A.d[i]); 101 return ret; 102 } 103 }t[N],b; 104 105 struct arr 106 { 107 int x,y,id; 108 }q[N],c[N]; 109 110 int a[N],ans[N]; 111 112 /*base merge(const base &n1,const base &n2) 113 { 114 base ret=n1; 115 for(int i=20;i>=0;i--) 116 if(n2.d[i]) ret.insert(n1.d[i]); 117 return ret; 118 }*/ 119 120 void solve(int l,int r,int x,int y) 121 { 122 if(l==r) 123 { 124 for(int i=x;i<=y;i++) ans[q[i].id]=a[l]; 125 return; 126 } 127 if(x>y) return; 128 int mid=(l+r)>>1; 129 memset(b.d,0,sizeof(b.d)); 130 for(int i=mid;i>=l;i--) 131 { 132 b.insert(a[i]); 133 for(int j=0;j<=20;j++) t[i].d[j]=b.d[j]; 134 } 135 memset(b.d,0,sizeof(b.d)); 136 for(int i=mid+1;i<=r;i++) 137 { 138 b.insert(a[i]); 139 for(int j=0;j<=20;j++) t[i].d[j]=b.d[j]; 140 } 141 int l1=x,r1=y; 142 for(int i=x;i<=y;i++) 143 { 144 if(q[i].y<=mid) c[l1++]=q[i]; 145 else if(q[i].x>mid) c[r1--]=q[i]; 146 else 147 { 148 base tmp=t[q[i].x]+t[q[i].y]; 149 ans[q[i].id]=tmp.query_max(); 150 } 151 } 152 for(int i=x;i<l1;i++) q[i]=c[i]; 153 for(int i=r1+1;i<=y;i++) q[i]=c[i]; 154 solve(l,mid,x,l1-1); 155 solve(mid+1,r,r1+1,y); 156 } 157 158 int main() 159 { 160 //freopen("cf1100f.in","r",stdin); 161 //freopen("cf1100f.out","w",stdout); 162 int n,m; 163 scanf("%d",&n); 164 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 165 scanf("%d",&m); 166 for(int i=1;i<=m;i++) 167 { 168 scanf("%d%d",&q[i].x,&q[i].y); 169 q[i].id=i; 170 } 171 solve(1,n,1,m); 172 for(int i=1;i<=m;i++) printf("%d ",ans[i]); 173 return 0; 174 }
做法2：假设固定右端点，维护log个维上使生成空间变大的最大的l
比做法1快3倍
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 typedef unsigned int uint; 5 typedef unsigned long long ull; 6 typedef pair<int,int> PII; 7 typedef pair<ll,ll> Pll; 8 typedef vector<int> VI; 9 typedef vector<PII> VII; 10 typedef pair<ll,int>P; 11 #define N 510000 12 #define M 151000 13 #define fi first 14 #define se second 15 #define MP make_pair 16 #define pi acos(-1) 17 #define mem(a,b) memset(a,b,sizeof(a)) 18 #define rep(i,a,b) for(int i=(int)a;i<=(int)b;i++) 19 #define per(i,a,b) for(int i=(int)a;i>=(int)b;i--) 20 #define lowbit(x) x&(-x) 21 #define Rand (rand()*(1<<16)+rand()) 22 #define id(x) ((x)<=B?(x):m-n/(x)+1) 23 #define ls p<<1 24 #define rs p<<1|1 25 26 const ll MOD=1e9+7,inv2=(MOD+1)/2; 27 double eps=1e-6; 28 ll INF=1e18; 29 ll inf=5e13; 30 int dx[4]={-1,1,0,0}; 31 int dy[4]={0,0,-1,1}; 32 33 int f[N][31],g[N][31],a[N]; 34 35 int read() 36 { 37 int v=0,f=1; 38 char c=getchar(); 39 while(c<48||57<c) {if(c=='-') f=-1; c=getchar();} 40 while(48<=c&&c<=57) v=(v<<3)+v+v+c-48,c=getchar(); 41 return v*f; 42 } 43 44 void add(int i,int x) 45 { 46 int k=i; 47 per(j,30,0) f[i][j]=f[i-1][j],g[i][j]=g[i-1][j]; 48 per(j,30,0) 49 if(x>>j) 50 { 51 if(!f[i][j]) 52 { 53 f[i][j]=x; 54 g[i][j]=k; 55 break; 56 } 57 else 58 { 59 if(k>g[i][j]) 60 { 61 swap(k,g[i][j]); 62 swap(x,f[i][j]); 63 } 64 x^=f[i][j]; 65 } 66 } 67 } 68 69 int main() 70 { 71 //freopen("1.in","r",stdin); 72 //freopen("1.out","w",stdout); 73 //int cas=read(); 74 //while(cas--) 75 //{ 76 int n=read(); 77 rep(i,1,n) 78 rep(j,0,30) f[i][j]=g[i][j]=0; 79 int lastans=0; 80 rep(i,1,n) 81 { 82 a[i]=read(); 83 add(i,a[i]); 84 } 85 int m=read(); 86 while(m--) 87 { 88 int l=read(),r=read(); 89 lastans=0; 90 per(i,30,0) 91 if((lastans^f[r][i])>lastans&&g[r][i]>=l) lastans^=f[r][i]; 92 printf("%d ",lastans); 93 } 94 95 //} 96 97 98 99 100 return 0; 101 }