牛客小白月赛9 C---红球进黑洞
Whiteying
2018-11-19 23:11:14
# A类
# 借鉴来源：
https://blog.csdn.net/qq_36778821/article/details/78725570
# 题目链接：
https://ac.nowcoder.com/acm/contest/275/C
# 题意：
有两种操作：
1. 求区间和
2. 区间异或
# 思路：
异或只跟每个二进制位有关，于是线段树储存区间内二进制各个位1的数量，异或一个数时，若某位是1，那么用区间长度减去原来的1数量就是异或后的1数量了。
# AC代码：
```cpp
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <queue>
#define ri(n) scanf("%d",&n)
#define oi(n) printf("%d\n",n)
#define rl(n) scanf("%lld",&n)
#define ol(n) printf("%lld\n",n)
#define rep(i,l,r) for(i=l;i<=r;i++)
#define rep1(i,l,r) for(i=l;i<r;i++)
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int epg=10-8;
const int maxn=1e5+10;
int val[maxn*4],a[maxn*4][25];
int x;
ll ans;
void uppush(int id)
{
for(int i=0; i<22; i++)
a[id][i]=a[id<<1][i]+a[id<<1|1][i];
}
void updown(int id,int sum)
{
if(val[id])
{
val[id<<1]^=val[id];
val[id<<1|1]^=val[id];
for(int i=0; i<22; i++)
{
if((val[id]>>i)&1)
{
a[id<<1][i]=sum-(sum>>1)-a[id<<1][i];
a[id<<1|1][i]=(sum>>1)-a[id<<1|1][i];
}
}
val[id]=0;
}
}
void build(int l,int r,int id)
{
if(l==r)
{
scanf("%d",&x);
for(int i=0; i<22; i++)
{
if((x>>i)&1)
a[id][i]=1;
else
a[id][i]=0;
}
return ;
}
int m=(l+r)>>1;
build(l,m,id<<1);
build(m+1,r,id<<1|1);
uppush(id);
}
void updata(int L,int R,int ad,int l,int r,int id)
{
if(L<=l&&R>=r)
{
val[id]^=ad;
for(int i=0; i<22; i++)
{
if((ad>>i)&1)
a[id][i]=r-l+1-a[id][i];
}
return ;
}
updown(id,r-l+1);
int m=(l+r)>>1;
if(L<=m)
updata(L,R,ad,l,m,id<<1);
if(R>m)
updata(L,R,ad,m+1,r,id<<1|1);
//updown(id,r-l+1);
uppush(id);
}
void query(int L,int R,int l,int r,int id)
{
if(L<=l&&R>=r)
{
for(int i=0; i<22; i++)
{
ans+=((ll)a[id][i]<<i);//真滴傻逼
}
return ;
}
updown(id,r-l+1);
int m=(l+r)>>1;
if(L<=m)
query(L,R,l,m,id<<1);
if(R>m)
query(L,R,m+1,r,id<<1|1);
//updown(id,r-l+1);
}
int main()
{
int n;
int m;
scanf("%d",&n);
scanf("%d",&m);
build(1,n,1);
int y,L,R,ad;
for(int i=1; i<=m; i++)
{
scanf("%d",&y);
if(y==1)
{
scanf("%d%d",&L,&R);
ans=0;
query(L,R,1,n,1);
printf("%lld\n",ans);
}
else
{
scanf("%d%d%d",&L,&R,&ad);
updata(L,R,ad,1,n,1);
}
}
return 0;
}
```