/*
reference:
translation:
solution:
trigger:
note:
*
record:
date:
2019.09.04
*/
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dwn(i,a,b) for(int i=a;i>=b;--i)
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x=f?-x:x;}
inline void write(int n){if(n==0)return;write(n/10);putchar(n%10+'0');}
#define mem(a,b) memset(a,b,sizeof(a))
#define ee(i,u) for(int i=head[u];i;i=e[i].next)
#define lson (o<<1)
#define rson (o<<1|1)
const int N=2e5+10,M=1e5+50,inf=0x3f3f3f3f;
int n,m,a[N],K[25];
struct tree{
int l,r;
int tg[25];bool val[25];
}t[N<<2];
inline void pushup(int o){
rep(i,0,20)
t[o].val[i]=t[lson].val[i]^t[rson].val[i];
}
inline void pushdown(int o,int l,int r){
int mid=l+r>>1;
rep(i,0,20){
if(t[o].tg[i]==0)continue;
if(t[o].tg[i]==1)
t[lson].val[i]=t[rson].val[i]=0;
else if(t[o].tg[i]==2)
t[lson].val[i]=(mid-l+1)&1,t[rson].val[i]=(r-mid)&1;//区间赋为1 异或和:奇为1 偶为0
t[lson].tg[i]=t[rson].tg[i]=t[o].tg[i];
t[o].tg[i]=0;
}
}
void And(int o,int l,int r,int x,int y){
if(l>y||r<x) return;
if(x<=l&&r<=y){
rep(i,0,20)
if(!K[i])
t[o].val[i]=0,t[o].tg[i]=1;
return;
}
pushdown(o,l,r);
int mid=l+r>>1;
And(lson,l,mid,x,y),And(rson,mid+1,r,x,y);
pushup(o);
}
void Or(int o,int l,int r,int x,int y){
if(l>y||r<x) return;
if(x<=l&&r<=y){
rep(i,0,20)
if(K[i])
t[o].val[i]=(r-l+1)&1,t[o].tg[i]=2;
return;
}
pushdown(o,l,r);
int mid=l+r>>1;
Or(lson,l,mid,x,y),Or(rson,mid+1,r,x,y);
pushup(o);
}
int Ans,ans[20];
void Xor(int o,int l,int r,int x,int y){
if(l>y||r<x) return;
if(x<=l&&r<=y){
rep(i,0,20)
ans[i]^=t[o].val[i];
return;
}
pushdown(o,l,r);
int mid=l+r>>1;
Xor(lson,l,mid,x,y);
Xor(rson,mid+1,r,x,y);
pushup(o);
}
void print(int l,int r){
Ans=0;
mem(ans,0);
Xor(1,1,n,l,r);
rep(i,0,20)
if(ans[i])
Ans|=(1<<i);
printf("%d
",Ans);
}
inline void build(int o,int l,int r){
t[o].l=l,t[o].r=r;
if(l==r){
rep(i,0,20)t[o].val[i]=(a[l]>>i)&1;
return ;
}
int mid=l+r>>1;
build(lson,l,mid);
build(rson,mid+1,r);
pushup(o);
}
int main(){
#ifdef WIN32
freopen("t3.txt","r",stdin);
//freopen("and.out","w",stdout);
#endif
rd(n),rd(m);
rep(i,1,n)rd(a[i]);
build(1,1,n);
while(m--){
int op,x,y,k;
rd(op);
if(op==3) rd(x),rd(y),print(x,y);
else{
rd(x),rd(y),rd(k);
rep(i,0,20)K[i]=(k>>i)&1;
if(op==1) And(1,1,n,x,y);
else if(op==2) Or(1,1,n,x,y);
}
}
printf("%.3lf M",(double)sizeof(t)/(1<<20));
return 0;
}
线段树+二进制位拆分【CF242E】XOR on Segment
/*
reference:
translation:
solution:
由于异或不具有叠加性,所以不能用lazylazy标记直接异或。
我们记录t[o].val[i]代表当前节点o,二进制位i上是1的数有多少个。
由于,如果某一二进制位上原来为1,且当前异或的数x的二进制位上也有1,
那么我们的当前t[o].val[i]=r-l+1-t[o].val[i]
可以理解为01交换。
然后由于2^20比10^6要大。所以只需要拆到20即可。
然后直接计算即可。
trigger:
note:
*
record:
date:
2019.09.07
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dwn(i,a,b) for(int i=a;i>=b;--i)
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x=f?-x:x;}
inline void write(int n){if(n==0)return;write(n/10);putchar(n%10+'0');}
#define mem(a,b) memset(a,b,sizeof(a))
#define ee(i,u) for(int i=head[u];i;i=e[i].next)
#define lson (o<<1)
#define rson (o<<1|1)
const int N=1e5+10;
int n,m;
struct tree{
int l,r;
int tag,val[21];
}t[N<<2];
inline void pushup(int o){
dwn(i,20,0)
t[o].val[i]=t[lson].val[i]+t[rson].val[i];
}
inline void build(int o,int l,int r){
t[o].l=l,t[o].r=r;
if(l==r){
int x;rd(x);
dwn(i,20,0)
if((x>>i)&1)
t[o].val[i]=1;
return ;
}
int mid=l+r>>1;
build(lson,l,mid);
build(rson,mid+1,r);
pushup(o);
}
inline void pushdown(int o){
if(t[o].tag==0)return ;
int l=t[o].l,r=t[o].r;
int mid=l+r>>1;
dwn(i,20,0){
if((t[o].tag>>i)&1){
t[lson].val[i]=mid-l+1-t[lson].val[i];
t[rson].val[i]=r-mid-t[rson].val[i];
}
}
t[lson].tag^=t[o].tag;//继承
t[rson].tag^=t[o].tag;
t[o].tag=0;//清零
}
inline void change(int o,int x,int y,int k){
int l=t[o].l,r=t[o].r;
if(x<=l && r<=y){
t[o].tag^=k;
dwn(i,20,0)
if((k>>i)&1)
t[o].val[i]=r-l+1-t[o].val[i];
return ;
}
pushdown(o);
int mid=l+r>>1;
if(x<=mid)change(lson,x,y,k);
if(mid<y)change(rson,x,y,k);
pushup(o);
}
inline int query(int o,int x,int y){
int l=t[o].l,r=t[o].r;
if(x<=l && r<=y){
int res=0;
dwn(i,20,0)
res+=(1<<i)*t[o].val[i];
return res;
}
pushdown(o);
int mid=l+r>>1;
int ans=0;
if(x<=mid)ans+=query(lson,x,y);
if(mid<y)ans+=query(rson,x,y);
return ans;
}
signed main(){
#ifdef WIN32
freopen("CF242E.txt","r",stdin);
#endif
rd(n);
build(1,1,n);
rd(m);
while(m--){
int op,l,r,x;
rd(op);
if(op==1){
rd(l),rd(r);
printf("%lld
",query(1,l,r));
}
else{
rd(l),rd(r),rd(x);
change(1,l,r,x);
}
}
// printf("%.3lf M",(double)sizeof(t)/(1<<20));
return 0;
}
/*
5
4 10 3 13 7
8
1 2 4
2 1 3 3
1 2 4
1 3 3
2 2 5 5
1 1 5
2 1 2 10
1 2 3
*/
/*
26
22
0
34
11
*/
/*
6
4 7 4 0 7 3
5
2 2 3 8
1 1 5
2 3 5 1
2 4 5 6
1 2 3
*/
/*
38
28
*/
/*
Description
给定一个长为n(n<=10^5)n(n<=10^5)的数组
数组里的数不超过10^6
有两种操作：
1:求sum[l,r];
2:对[l,r]中的所有数^x
Input
第一行一个整数nn,代表有一个长度为nn的数组。
第二行nn个整数,代表aiai
第三行为一个整数mm,代表有mm次操作。
接下来mm行每行描述一个操作。
Output
对于每一个操作11,输出一行代表sum[l,r]sum[l,r].
*/