https://codeforces.com/contest/587/problem/E
一个序列,
1区间异或操作
2查询区间子集异或种类数
题解
解题思路大同小异,都是利用异或的性质进行转化,std和很多网友用的都是差分的思想,用两棵线段树
第一棵维护差分序列上的线性基,第二棵维护原序列的异或区间和,两者同时进行修改
考虑两个序列 $(a,b)(d,e)$,按照std的想法,应该是维护$(0 \^ a,a \^ b)(0 \^ d,d \^ e)$ 然后合并首尾变成$(0 \^ a,a \^ b,b \^ d,d \^ e)$
但由于异或的性质,我们直接每个区间保存下区间左端点原来的信息,
直接先插入两个序列的线性基,然后新头部的异或和即可,也就是$(0 \^a,a \^b,a \^ d,d \^e)$
写起来更加轻松
#include <bits/stdc++.h>
#define endl '\n'
#define ll long long
#define ull unsigned long long
#define fi first
#define se second
#define mp make_pair
#define pii pair<ll,ll>
#define all(x) x.begin(),x.end()
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define rep(ii,a,b) for(register int ii=a;ii<=b;++ii)
#define per(ii,a,b) for(register int ii=b;ii>=a;--ii)
#define forn(ii,x) for(int ii=head[x];ii;ii=e[ii].next)
#define show(x) cout<<#x<<"="<<x<<endl
#define show2(x,y) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl
#define show3(x,y,z) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
#define show4(w,x,y,z) cout<<#w<<"="<<w<<" "<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
#define show5(v,w,x,y,z) cout<<#v<<" "<<v<<" "<<#w<<"="<<w<<" "<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl
#define showa(a,b) cout<<#a<<'['<<b<<"]="<<a[b]<<endl
using namespace std;
const int maxn=2e5+10,maxm=2e5+10;
const int INF=0x3f3f3f3f;
const ll mod=1e9+7;
const double PI=acos(-1.0);
//heads
int casn,n,m,k;
class segtree{public:
#define nd node[now]
#define ndl node[now<<1]
#define ndr node[now<<1|1]
struct segnode{
int l,r,flag,val;
int d[32];
inline void init(){val=flag=0;memset(d,0,sizeof d);}
inline void insert(ll x){
for(register int i=30;x&&i>=0;--i)
if(x&(1ll<<i)){
if(!d[i]) {d[i]=x;return;}
else x^=d[i];
}
}
int count(){int ans=0;per(i,0,30) if(d[i])ans++; return ans;}
void update(int x){val^=x;flag^=x;}
}node[maxn<<2|3];
inline segnode marge(segnode &a,segnode b)const {
segnode ans;ans.init();
per(i,0,30) ans.insert(a.d[i]),ans.insert(b.d[i]);
ans.insert(a.val^b.val);
ans.val=a.val;
ans.l=a.l,ans.r=b.r;
return ans;
}
inline void down(int now){
if(nd.flag){
ndl.update(nd.flag);ndr.update(nd.flag);
nd.flag=0;
}
}
void maketree(int s,int t,int now=1){
nd.l=s,nd.r=t;nd.init();
if(s==t) {cin>>nd.val;return ;}
maketree(s,(s+t)/2,now<<1);
maketree((s+t)/2+1,t,now<<1|1);
nd=marge(ndl,ndr);
}
void update(int s,int t,int x,int now=1){
if(s<=nd.l&&t>=nd.r) {nd.update(x);return;}
down(now);
if(s<=ndl.r) update(s,t,x,now<<1);
if(t>ndl.r) update(s,t,x,now<<1|1);
nd=marge(ndl,ndr);
}
segnode query(int s,int t,int now=1){
if(s<=nd.l&&t>=nd.r) {
if(s==nd.l) {
segnode x;x.init();
return marge(x,nd);
}else return nd;
}
down(now);
segnode ans;ans.init();
if(s<=ndl.r) ans=marge(ans,query(s,t,now<<1));
if(t>ndl.r) ans=marge(ans,query(s,t,now<<1|1));
nd=marge(ndl,ndr);
return ans;
}
}tree;
int main() {
IO;
cin>>n>>m;
register int a,b,c,d;
tree.maketree(1,n);
while(m--){
cin>>a>>b>>c;
if(a==1){
cin>>d;tree.update(b,c,d);
}else cout<<(1<<tree.query(b,c).count())<<endl;
}
}