[Ynoi2013] 无力回天 NOI2017
首先看到异或，想到能维护异或的东西就那几样（线性基/01trie/数位 dp/FWT），再看到求选任意个数后的异或最大值，线性基无疑了。
这时再看还要维护什么其它信息，区间异或，区间查询，一副线段树维护线性基的样子。但我们知道线性基中的值一旦修改就必须重构，区间修改的时间复杂度不允许，尝试优化这个做法。
可以发现虽然不允许区间修改，但允许单点修改。区间转单点，想到了什么？差分！考虑令 \(b\) 表示原数组的异或差分数组，即 \(b_i=\begin{cases}a_i&\text{若}\ i=1\\a_{i-1}\oplus a_i&\text{若}\ i\not=1\end{cases}\)。反过来，\(a_i\) 为 \(b\) 的异或前缀和。可以发现每次区间异或操作相当于修改 \(b_l\) 和 \(b_{r+1}\) 两个值。
又因为若线性基中的数能表示 \(a_{i-1}\)，那么再插入一个 \(b_i\) 一定能够表示 \(a_i\)。所以 \(\{a_l,a_{l+1},a_{l+2},\dots,a_r\}\) 的线性基等价于在 \(\{b_{l+1},b_{l+2},\dots,b_r\}\) 的线性基中插入 \(a_l\) 后的线性基。因此用线段树维护 \(b_l,b_{l+1},b_{l+2},\dots,b_r\) 的线性基，每次修改操作重构 \(l\) 和 \(r+1\) 处的线性基即可。复杂度 \(O(n\log^3n)\)
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=5e4+10,Lg=30;
int a[N],b[N],n,q;
struct base{
int p[35];
void ins(int &x){
for(int i=Lg;i>=0;i--){
if(x>>i&1){
if(!p[i]){
p[i]=x;
break;
}
else{
x^=p[i];
}
}
}
}
void clear(){
for(int i=Lg;i>=0;i--){
p[i]=0;
}
}
int query(int mx){
for(int i=Lg;i>=0;i--){
if((mx^p[i])>=mx){
mx^=p[i];
}
}
return mx;
}
};
base merge(base x,base y){
for(int i=Lg;i>=0;i--){
x.ins(y.p[i]);
}
return x;
}
namespace Seg_Tree{
base ans[N<<2];
#define ls(p) p<<1
#define rs(p) p<<1|1
void push_up(int p){
ans[p]=merge(ans[ls(p)],ans[rs(p)]);
}
void build(int p,int l,int r){
if(l==r){
ans[p].ins(b[l]);
return;
}
int mid=(l+r)>>1;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
push_up(p);
}
void update(int p,int l,int r,int pos,int val){
if(l==r){
ans[p].clear();
b[l]^=val;
ans[p].ins(b[l]);
return;
}
int mid=(l+r)>>1;
if(pos<=mid){
update(ls(p),l,mid,pos,val);
}
else{
update(rs(p),mid+1,r,pos,val);
}
push_up(p);
}
base query(int p,int l,int r,int q_l,int q_r){
if(q_l<=l&&r<=q_r){
return ans[p];
}
int mid=(l+r)>>1;
if(q_r<=mid){
return query(ls(p),l,mid,q_l,q_r);
}
if(q_l>mid){
return query(rs(p),mid+1,r,q_l,q_r);
}
return merge(query(ls(p),l,mid,q_l,q_r),query(rs(p),mid+1,r,q_l,q_r));
}
}
namespace Fenwick_Tree{
int ans[N];
int lowbit(int x){
return x&(-x);
}
void update(int pos,int val){
while(pos<=n){
ans[pos]^=val;
pos+=lowbit(pos);
}
}
int query(int pos){
int res=0;
while(pos){
res^=ans[pos];
pos-=lowbit(pos);
}
return res;
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
read(n),read(q);
for(int i=1;i<=n;i++){
read(a[i]);
b[i]=a[i]^a[i-1];
}
Seg_Tree::build(1,1,n);
for(int i=1;i<=n;i++){
Fenwick_Tree::update(i,b[i]);
}
while(q--){
int opt,l,r,val;
read(opt),read(l),read(r),read(val);
if(opt==1){
Seg_Tree::update(1,1,n,l,val);
Fenwick_Tree::update(l,val);
if(r<n){
Seg_Tree::update(1,1,n,r+1,val);
Fenwick_Tree::update(r+1,val);
}
}
else{
int x=Fenwick_Tree::query(l);
base y;
y.clear();
if(l!=r){
y=Seg_Tree::query(1,1,n,l+1,r);
}
y.ins(x);
write_endl(y.query(val));
}
}
return 0;
}