网站霸词怎么做,合肥网站建设设计公司,wordpress 顶部空白,免费游戏网站建设传送门:牛客
题目描述:
区间求和区间异或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一道区间求和区间异或的题目,可以称得上是线段树的一道好题
首先对于异或运算来说,并不满足…传送门:牛客
题目描述:
区间求和区间异或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一道区间求和区间异或的题目,可以称得上是线段树的一道好题
首先对于异或运算来说,并不满足区间分配率,也就是说对于(ab)(ab)(ab)^c≠c\neqc aaa^c bbb^c,那么对于此时的区间异或来说,我们似乎没有了求出对和的贡献的方法.
我们需要换一种思路去思考这道题.对于异或来说,一般关于异或的题目总是在二进制数上面出题目的.我们想一下对于一个区间的每一个数字来说,我们将原本的十进制加法变成二进制加法是不是也是可以的.那么对于二进制加法来说,我们需要知道什么?显然我们需要知道每一位区间内所有数字在这一位是111的个数.只要我们知道每一位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 rt1
#define rs rt1|1
#define lson l,mid,rt1
#define rson mid1,r,rt1|1
inline ll read() {ll x0,w1;char chgetchar();for(;ch9||ch0;chgetchar()) if(ch-) w-1;for(;ch0ch9;chgetchar()) xx*10ch-0;return x*w;
}
#define int long long
#define maxn 100100
const double eps1e-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.suml.sumr.sum;for(int i0;i32;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].ll;tree[rt].rr;if(lr) {tree[rt].suma[l];int va[l];int cnt0;while(v) {if(v1) tree[rt].bit1[cnt]1;else tree[rt].bit0[cnt]1;cnt;v1;}if(v0) {//注意这里,我们必须要求出所有的32位,因为对于0的位置我们依旧需要记录该位置有0//当时就是这一步忽略了,导致我调试了几个小时!!while(cnt32) {tree[rt].bit0[cnt]1;cnt;}}return ;}int mid(lr)1;build(lson);build(rson);pushup(rt);
}
int get_num(int rt) {int SUM[34]{0};int jw0;for(int i0;i32;i) {SUM[i](tree[rt].bit1[i]jw)%2;jw(tree[rt].bit1[i]jw)/2;}int ans0;int k1;for(int i0;i32;i) {ansk*SUM[i];k*2;}return ans;
}
void change(int rt,int v) {tree[rt].lazy^v;for(int i0;i32;i) {if(v1) {swap(tree[rt].bit1[i],tree[rt].bit0[i]);}v1;if(v0) break;}tree[rt].sumget_num(rt);
}
void pushdown(int rt) {change(ls,tree[rt].lazy);change(rs,tree[rt].lazy);tree[rt].lazy0;
}
void update(int l,int r,int v,int rt) {if(tree[rt].lltree[rt].rr) {change(rt,v);return ;}if(tree[rt].lazy) pushdown(rt);int mid(tree[rt].ltree[rt].r)1;if(rmid) update(l,r,v,ls);else if(lmid) update(l,r,v,rs);else update(l,mid,v,ls),update(mid1,r,v,rs);pushup(rt);
}
Segment_tree query(int l,int r,int rt) {if(tree[rt].lltree[rt].rr) {return tree[rt];}if(tree[rt].lazy) pushdown(rt);int mid(tree[rt].ltree[rt].r)1;if(rmid) return query(l,r,ls);else if(lmid) return query(l,r,rs);else {auto Leftquery(l,mid,ls);auto Rightquery(mid1,r,rs);Segment_tree Ans;pushup(Ans,Left,Right);return Ans;}
}
signed main() {nread();mread();for(int i1;in;i) a[i]read();build(root);for(int i1;im;i) {int optread();if(opt1) {int lread(),rread();printf(%lld\n,query(l,r,1).sum);}else {int lread(),rread(),kread();update(l,r,k,1);}}return 0;
}
