这题其实挺经典的，看到求异或最大，显然想到的是线性基，不过这怎么维护？当然区间有关的东西都可以上线段树，区间修改时记录每个点的修改量k，然后合并线性基时再加入线性基。因为线性基是求一组极大线性无关组，所以查询a[i]^k组成的线性基等价于查询k∪a[i]。
#include<bits/stdc++.h> #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 using namespace std; const int N=5e4+7; struct base{ int p[32],k; void clear(){memset(p,0,sizeof p);} void insert(int x) { for(int i=30;~i;i--) if(x>>i&1) { if(p[i])x^=p[i]; else{p[i]=x;break;} } } int ask(int x) { int ret=x; for(int i=30;~i;i--)ret=max(ret^p[i],ret); return ret; } }tr[N<<2],ans; int n,m,lazy[N<<2]; base merge(base a,base b) { base ret=a; for(int i=30;~i;i--)if(b.p[i])ret.insert(b.p[i]); ret.insert(ret.k^b.k); return ret; } void modify(int rt,int v){tr[rt].k^=v,lazy[rt]^=v;} void pushdown(int rt){modify(rt<<1,lazy[rt]),modify(rt<<1|1,lazy[rt]),lazy[rt]=0;} void build(int l,int r,int rt) { if(l==r){scanf("%d",&tr[rt].k);return;} int mid=l+r>>1; build(lson),build(rson); tr[rt]=merge(tr[rt<<1],tr[rt<<1|1]); } void update(int L,int R,int v,int l,int r,int rt) { if(L<=l&&r<=R){modify(rt,v);return;} pushdown(rt); int mid=l+r>>1; if(L<=mid)update(L,R,v,lson); if(R>mid)update(L,R,v,rson); tr[rt]=merge(tr[rt<<1],tr[rt<<1|1]); } void query(int L,int R,int l,int r,int rt) { if(L<=l&&r<=R){ans=merge(ans,tr[rt]);return;} pushdown(rt); int mid=l+r>>1; if(L<=mid)query(L,R,lson); if(R>mid)query(L,R,rson); } int main() { scanf("%d%d",&n,&m); build(1,n,1); while(m--) { int op,l,r,v;scanf("%d%d%d%d",&op,&l,&r,&v); if(op==1)update(l,r,v,1,n,1); else ans.clear(),query(l,r,1,n,1),printf("%d\n",ans.ask(v)); } }
原文：https://www.cnblogs.com/hfctf0210/p/11027275.html
