做兼职的设计网站有哪些,企业形象设计课程,网站配置域名解析,怎样自己做网站模板正题
题目链接:https://www.luogu.com.cn/problem/P5607 题目大意 nnn个数字的序列#xff0c;mmm次操作
区间[l,r][l,r][l,r]异或上一个值vvv询问区间[l,r][l,r][l,r]中选出一些数来异或的最大异或和 解题思路
最大异或和的话只能是线性基了#xff0c;但是线性基的区间修…正题
题目链接:https://www.luogu.com.cn/problem/P5607 题目大意
nnn个数字的序列mmm次操作
区间[l,r][l,r][l,r]异或上一个值vvv询问区间[l,r][l,r][l,r]中选出一些数来异或的最大异或和 解题思路
最大异或和的话只能是线性基了但是线性基的区间修改又不能通过打标记的方法。
不能区间修改就转单点修改我们定义一个序列biaixorai−1b_ia_i\ xor\ a_{i-1}biai xor ai−1。这样修改的时候就可以单点进行修改了。
但是这样好像会影响我们的查询操作考虑查询区间[l,r][l,r][l,r]的时候我们会选出若干个前缀来进行操作被异或多次的区间会抵消掉一些如果选择了bxb_xbx就可以理解为选择了ax−1xoraxa_{x-1}\ xor\ a_{x}ax−1 xor ax。
但是会发现b1∼lb_{1\sim l}b1∼l也就是ala_lal可能会被异或很多次其实可以把bl1∼r∪alb_{l1\sim r}\cup a_lbl1∼r∪al的线性基拿出来跑就是答案了。因为如果在[l1,r][l1,r][l1,r]这个范围无论选择了奇偶个都可以用ala_lal来决定前面区间的异或次数。
ala_lal的话我们再维护一个树状数组来查询就好了注意一下细节就行了
时间复杂度O((nm)lognlog2w)O((nm)\log n\log^2 w)O((nm)lognlog2w) code
#includecstdio
#includecstring
#includealgorithm
#define lowbit(x) (x-x)
using namespace std;
const int N5e410;
struct xxj{int d[32];void init(){memset(d,0,sizeof(d));}void Insert(int x){for(int i30;i0;i--)if((xi)1){if(d[i])x^d[i];else{d[i]x;return;}}return;}int Query(int x){for(int i30;i0;i--)if((x^d[i])x)x^d[i];return x;}
}c,w[N2],ans;
int n,m,a[N],t[N];
void Add(xxj a,xxj b){for(int i0;i30;i)if(b.d[i])a.Insert(b.d[i]);return;
}
void Change(int x,int L,int R,int pos,int val){if(LR){w[x].init();a[L]^val;w[x].Insert(a[L]);return;}int mid(LR)1;if(posmid)Change(x*2,L,mid,pos,val);else Change(x*21,mid1,R,pos,val);w[x]w[x*2];Add(w[x],w[x*21]);return;
}
void Ask(int x,int L,int R,int l,int r){if(LlRr){Add(ans,w[x]);return;}int mid(LR)1;if(rmid)Ask(x*2,L,mid,l,r);else if(lmid)Ask(x*21,mid1,R,l,r);else Ask(x*2,L,mid,l,mid),Ask(x*21,mid1,R,mid1,r);return;
}
void Change(int x,int val){while(xn){t[x]^val;xlowbit(x);}return;
}
int Ask(int x){int ans0;while(x){ans^t[x];x-lowbit(x);}return ans;
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i)scanf(%d,a[i]);for(int in;i1;i--){int pa[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(op1){Change(l,x);Change(r1,x);Change(1,1,n,l,x);if(rn)Change(1,1,n,r1,x);}else{ans.init();if(lr)Ask(1,1,n,l1,r);int mxans.Query(x);mxmax(mx,ans.Query(x^Ask(l)));printf(%d\n,mx);}}return 0;
}
