视频链接:G73 线段树+线性基合并 P5607 [Ynoi2013] 无力回天 NOI2017_哔哩哔哩_bilibili
P5607 [Ynoi2013] 无力回天 NOI2017 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
// 线段树+线性基合并 O(n*logn*logv*logv) #include <iostream> #include <cstring> #include <algorithm> using namespace std; #define ls (u<<1) #define rs (u<<1|1) #define mid (l+r>>1) const int N=50005; int a[N],n,m; struct Tree{ int p[31]; //区间线性基 int s; //区间异或和 void clear(){memset(p,0,sizeof p);} void insert(int x){ //插入基 for(int i=30;i>=0;--i) if(x>>i&1){ if(!p[i]){p[i]=x;break;} x^=p[i]; } } }tr[N<<2]; //节点 Tree merge(Tree a,Tree b){ //合并基 Tree c; c.clear(); //清空基数组 for(int i=30;i>=0;--i) if(a.p[i]) c.p[i]=a.p[i]; else if(b.p[i]) c.p[i]=b.p[i]; for(int i=30;i>=0;--i) if(a.p[i]&&b.p[i]) c.insert(b.p[i]); c.s=a.s^b.s; return c; } void build(int u,int l,int r){ //建树 if(l==r){tr[u].insert(tr[u].s=a[l]);return;} build(ls,l,mid); build(rs,mid+1,r); tr[u]=merge(tr[ls],tr[rs]); } void change(int u,int l,int r,int pos,int x){ //点修 if(l==r){ tr[u].clear(); //清空基数组 tr[u].insert(tr[u].s^=x); return; } if(pos<=mid) change(ls,l,mid,pos,x); else change(rs,mid+1,r,pos,x); tr[u]=merge(tr[ls],tr[rs]); } int sum(int u,int l,int r,int pos){ //前缀和 if(l==r) return tr[u].s; if(pos<=mid) return sum(ls,l,mid,pos); else return sum(rs,mid+1,r,pos)^tr[ls].s; } Tree ask(int u,int l,int r,int L,int R){ //区查 if(L<=l&&r<=R) return tr[u]; if(L>mid) return ask(rs,mid+1,r,L,R); if(R<=mid) return ask(ls,l,mid,L,R); return merge(ask(ls,l,mid,L,R),ask(rs,mid+1,r,L,R)); } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) scanf("%d",&a[i]); for(int i=n-1;i;--i) a[i+1]^=a[i]; //转成差分数组 build(1,1,n); for(int opt,l,r,v;m--;){ scanf("%d%d%d%d",&opt,&l,&r,&v); if(opt==1){ change(1,1,n,l,v); //点修l if(r<n) change(1,1,n,r+1,v); //点修r+1 } else{ int s=sum(1,1,n,l); //求a[l] if(l==r) printf("%d\n",max(v,v^s)); else{ Tree t=ask(1,1,n,l+1,r); //求b[l+1...r] t.insert(s); //插入a[l] for(int i=30;i>=0;--i) v=max(v,v^t.p[i]); printf("%d\n",v); } } } }
标签:P5607,return,int,void,Ynoi2013,tr,NOI2017 From: https://www.cnblogs.com/dx123/p/18328599