正题
题目链接:https://www.luogu.com.cn/problem/P5607
题目大意
(n)个数字的序列，(m)次操作
- 区间([l,r])异或上一个值(v)
- 询问区间([l,r])中选出一些数来异或的最大异或和
解题思路
最大异或和的话只能是线性基了，但是线性基的区间修改又不能通过打标记的方法。
不能区间修改就转单点修改，我们定义一个序列(b_i=a_i xor a_{i-1})。这样修改的时候就可以单点进行修改了。
但是这样好像会影响我们的查询操作，考虑查询区间([l,r])的时候，我们会选出若干个前缀来进行操作，被异或多次的区间会抵消掉一些，如果选择了(b_x)就可以理解为选择了(a_{x-1} xor a_{x})。
但是会发现(b_{1sim l})也就是(a_l)可能会被异或很多次，其实可以把(b_{l+1sim r}cup a_l)的线性基拿出来跑就是答案了。因为如果在([l+1,r])这个范围无论选择了奇偶个都可以用(a_l)来决定前面区间的异或次数。
(a_l)的话我们再维护一个树状数组来查询就好了，注意一下细节就行了
时间复杂度(O((n+m)log nlog^2 w))
code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lowbit(x) (x&-x)
using namespace std;
const int N=5e4+10;
struct xxj{
int d[32];
void init(){memset(d,0,sizeof(d));}
void Insert(int x){
for(int i=30;i>=0;i--)
if((x>>i)&1){
if(d[i])x^=d[i];
else{
d[i]=x;
return;
}
}
return;
}
int Query(int x){
for(int i=30;i>=0;i--)
if((x^d[i])>x)x^=d[i];
return x;
}
}c,w[N<<2],ans;
int n,m,a[N],t[N];
void Add(xxj &a,xxj &b){
for(int i=0;i<=30;i++)
if(b.d[i])a.Insert(b.d[i]);
return;
}
void Change(int x,int L,int R,int pos,int val){
if(L==R){w[x].init();a[L]^=val;w[x].Insert(a[L]);return;}
int mid=(L+R)>>1;
if(pos<=mid)Change(x*2,L,mid,pos,val);
else Change(x*2+1,mid+1,R,pos,val);
w[x]=w[x*2];Add(w[x],w[x*2+1]);
return;
}
void Ask(int x,int L,int R,int l,int r){
if(L==l&&R==r){Add(ans,w[x]);return;}
int mid=(L+R)>>1;
if(r<=mid)Ask(x*2,L,mid,l,r);
else if(l>mid)Ask(x*2+1,mid+1,R,l,r);
else Ask(x*2,L,mid,l,mid),Ask(x*2+1,mid+1,R,mid+1,r);
return;
}
void Change(int x,int val){
while(x<=n){
t[x]^=val;
x+=lowbit(x);
}
return;
}
int Ask(int x){
int ans=0;
while(x){
ans^=t[x];
x-=lowbit(x);
}
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=n;i>=1;i--){
int p=a[i]^a[i-1];a[i]=0;
Change(1,1,n,i,p);Change(i,p);
}
while(m--){
int op,l,r,x;
scanf("%d%d%d%d",&op,&l,&r,&x);
if(op==1){
Change(l,x);Change(r+1,x);
Change(1,1,n,l,x);
if(r<n)Change(1,1,n,r+1,x);
}
else{
ans.init();
if(l<r)Ask(1,1,n,l+1,r);
int mx=ans.Query(x);
mx=max(mx,ans.Query(x^Ask(l)));
printf("%d
",mx);
}
}
return 0;
}