刷题记录:牛客NC19429红球进黑洞 区间拆位异或+区间求和

传送门:牛客

题目描述:

区间求和+区间异或k
输入:
10 10
8 5 8 9 3 9 8 3 3 6 
2 1 4 1
1 2 6 
2 9 10 8
1 1 7 
2 4 7 8
2 8 8 6
2 2 3 0
1 1 2 
2 9 10 4
1 2 3 
输出:
33
50
13
13

一道区间求和+区间异或的题目,可以称得上是线段树的一道好题

首先对于异或运算来说,并不满足区间分配率,也就是说对于$(a+b)$^$c\ne$ $a$^c + $b$^c,那么对于此时的区间异或来说,我们似乎没有了求出对和的贡献的方法.

我们需要换一种思路去思考这道题.对于异或来说,一般关于异或的题目总是在二进制数上面出题目的.我们想一下对于一个区间的每一个数字来说,我们将原本的十进制加法变成二进制加法是不是也是可以的.那么对于二进制加法来说,我们需要知道什么?显然我们需要知道每一位区间内所有数字在这一位是$1$的个数.只要我们知道每一位1的个数,那么我们进行加法也就不难了.

因此我们此时可以使用线段树来存储每一个区间中的每一位的1的个数和0的个数.(根据数据范围来看,我们此时存储32位即可).这样想的话这道题就变得很明了了,我们记录了一个区间中每一位的0和1的个数,那么对于我们的区间异或k来说,我们只要知道k的二进制位中哪一个数字是1哪一个数字是0即可.因为对于异或来说,0不改变,1会使原数取反,那么对于有1的位置,那么就意味着那一个位置的0与1的个数调换一下即可.并且对于异或操作来说,我们满足结合律的性质,意味着我们可以用懒标记来记录我们的区间异或

具体细节可以参考代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
#define int long long
#define maxn 100100
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
struct Segment_tree{int l,r,lazy,bit0[34],sum,bit1[34];
}tree[maxn*4];
int n,m;int a[maxn];
void pushup(Segment_tree &u,Segment_tree &l,Segment_tree &r) {u.sum=l.sum+r.sum;for(int i=0;i<=32;i++) {u.bit0[i]=l.bit0[i]+r.bit0[i];u.bit1[i]=l.bit1[i]+r.bit1[i];}
}
void pushup(int rt) {pushup(tree[rt],tree[ls],tree[rs]);
}
void build(int l,int r,int rt) {tree[rt].l=l;tree[rt].r=r;if(l==r) {tree[rt].sum=a[l];int v=a[l];int cnt=0;while(v) {if(v&1) tree[rt].bit1[cnt]=1;else tree[rt].bit0[cnt]=1;cnt++;v>>=1;}if(v==0) {//注意这里,我们必须要求出所有的32位,因为对于0的位置我们依旧需要记录该位置有0//当时就是这一步忽略了,导致我调试了几个小时!!while(cnt<=32) {tree[rt].bit0[cnt]=1;cnt++;}}return ;}int mid=(l+r)>>1;build(lson);build(rson);pushup(rt);
}
int get_num(int rt) {int SUM[34]={0};int jw=0;for(int i=0;i<=32;i++) {SUM[i]=(tree[rt].bit1[i]+jw)%2;jw=(tree[rt].bit1[i]+jw)/2;}int ans=0;int k=1;for(int i=0;i<=32;i++) {ans+=k*SUM[i];k*=2;}return ans;
}
void change(int rt,int v) {tree[rt].lazy^=v;for(int i=0;i<=32;i++) {if(v&1) {swap(tree[rt].bit1[i],tree[rt].bit0[i]);}v>>=1;if(v==0) break;}tree[rt].sum=get_num(rt);
}
void pushdown(int rt) {change(ls,tree[rt].lazy);change(rs,tree[rt].lazy);tree[rt].lazy=0;
}
void update(int l,int r,int v,int rt) {if(tree[rt].l==l&&tree[rt].r==r) {change(rt,v);return ;}if(tree[rt].lazy) pushdown(rt);int mid=(tree[rt].l+tree[rt].r)>>1;if(r<=mid) update(l,r,v,ls);else if(l>mid) update(l,r,v,rs);else update(l,mid,v,ls),update(mid+1,r,v,rs);pushup(rt);
}
Segment_tree query(int l,int r,int rt) {if(tree[rt].l==l&&tree[rt].r==r) {return tree[rt];}if(tree[rt].lazy) pushdown(rt);int mid=(tree[rt].l+tree[rt].r)>>1;if(r<=mid) return query(l,r,ls);else if(l>mid) return query(l,r,rs);else {auto Left=query(l,mid,ls);auto Right=query(mid+1,r,rs);Segment_tree Ans;pushup(Ans,Left,Right);return Ans;}
}
signed main() {n=read();m=read();for(int i=1;i<=n;i++) a[i]=read();build(root);for(int i=1;i<=m;i++) {int opt=read();if(opt==1) {int l=read(),r=read();printf("%lld\n",query(l,r,1).sum);}else {int l=read(),r=read(),k=read();update(l,r,k,1);}}return 0;
}