传送门
题目大意：初始有一个序列a，有q个询问，每次询问 k | [l,r] 区间内子集异或的值的最大值是多少。
思路：根据题意，选取一部分值得到异或最大值，可以想到线性基，但是最后要OR上k，所以要消除k对其影响，我们就把每个数转化成二进制，然后将k为1的位置对于每个数其位置就变为0，这样就可以消除其k的影响了，最后在OR上k变回来，即为正确答案。比如数a[i]=6(110) ,k = 4(100),则a[i]应该变为(010)=2这样来消除k的影响。由于多次区间询问，所以用线段树维护一下即可。（常数优化不可忽视）
嗯...可以当做一个模板
#include<iostream> #include<algorithm> #include<cmath> #include<cstdio> #include<cstring> #define ll long long using namespace std; #include<iostream> using namespace std; const int maxn=1e4+10; int k; struct node{ int d[31],cnt; node(){memset(d,0,sizeof(d));cnt=0;} void insert(int x) { for(int i=30;i>=0;i--) { if(x>>i) { if(!d[i]) { d[i]=x; cnt++; break; } else x^=d[i]; } } } }a[maxn<<2]; node merge(node u,node v) { if(u.cnt==31)// 注意范围 return u; if(v.cnt==31)// 注意范围 return v; for(int i=30;i>=0;i--) { if(v.d[i]) u.insert(v.d[i]); } return u; } node query(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R) { return a[rt]; } node tt; int mid=(l+r)/2; if(L<=mid) tt=merge(tt,query(L,R,l,mid,rt<<1)); if(R>mid) tt=merge(tt,query(L,R,mid+1,r,rt<<1|1)); return tt; } int qmax(node tt) { int ans=k; for(int i=30;i>=0;i--) { if((ans^tt.d[i])>ans) ans^=tt.d[i]; } return ans; } void build(int l,int r,int rt) { if(l==r) { int tp; scanf("%d",&tp); tp&=k; a[rt].insert(tp); return ; } int mid=(l+r)>>1; build(l,mid,rt<<1); build(mid+1,r,rt<<1|1); a[rt]=merge(a[rt<<1],a[rt<<1|1]); } int main() { int t,n,q,l,r; scanf("%d",&t); while(t--) { node(); scanf("%d%d%d",&n,&q,&k); k=~k; build(1,n,1); k=~k; while(q--) { scanf("%d%d",&l,&r); node tt=query(l,r,1,n,1); printf("%d\n",qmax(tt)); } } return 0; }
