# Codeforces cf242e (codeforces round 149 div.2 problem E)

2021-05-04 14:11:59

## Understanding of topic meaning

Not many $$CodeForces$$ The title above is simple and easy to understand .
Let you maintain a length of $$n$$ Sequence , Two operations need to be supported , One is interval XOR , That is, for any $$i\in [l,r]$$, We need to $$a[i]\ xor\ x$$.
The second is a basic interval summation .
Data range ：$$n\le 1e5$$,$$m\le 5e4$$,$$a[i],x[i]\le 1e6$$.

## Their thinking

This problem belongs to the advanced problem of line segment tree , For those who don't know much about line segment trees, you can Learn about line segment trees .
XOR this thing is very troublesome , Because you can't record it like add subtract multiply divide $$tag$$ And then run $$lazy-tag$$, So we need to find a new way out . In fact, this problem brings a lot of harvest , Let's consider the XOR operation , For numbers $$a$$ and $$b$$ Think about it for everyone . So, can we just follow suit according to this nature ？
We found that , The data range given in the title is $$10^6$$, Just like $$2^{20}$$ A little smaller , in other words , If we do binary division for each number , It only needs $$20$$ That's enough space . therefore , We can consider how to maintain this thing with a line segment tree . We drive $$21$$ A line tree , Each line tree contains a binary bit of these numbers ,$$20$$ You can meet the requirements of the topic .

After the tree is confirmed, we will consider how to build it .
For the nature of our group of trees , Obviously, it takes one person to build . In fact, one more from each time $$1$$ To $$21$$ The cycle of , It looks like this duck's ：
for(int i=1;i<=21;i++) t[u][i].l=l,t[u][i].r=r;
If $$l==r$$, That is, leaf node , So we find that's what we need $$21$$ Every tree has its own boundaries , The one who deals with himself alone , in other words , If the current one $$a[l]$$ Of the $$k$$ position （ Binary digit ） yes $$1$$, So directly $$t[u][k].sum=1;$$
After that $$pushup$$ Part of it is the same , Need to cycle $$21$$ Time .
Build part of the code ：

void BuildTree(int u,int l,int r)
{
for(int i=1;i<=21;i++) t[u][i].l=l,t[u][i].r=r;
if(l==r)
{
for(int i=1;i<=21;i++) if(a[l]&(1<<(i-1))) t[u][i].sum=1;
return ;
}
int mid=(l+r)>>1;
BuildTree(u*2,l,mid);
BuildTree(u*2+1,mid+1,r);
for(int i=1;i<=21;i++) t[u][i].sum=t[u*2][i].sum+t[u*2+1][i].sum;
}


After the completion of the construction, we will consider how to modify the interval .
For this topic, input data provided by , Numbers that need to be XOR $$x$$ Come on , If $$x$$ One of the binary bits of is $$0$$, because $$0$$ XOR any number is the number itself , So you don't have to deal with it . If a binary bit is $$1$$, So obviously this $$1$$ To do a calculation with someone else , So if and only if ：
for(int i=1;1<<(i-1)<=x;i++) if(x&(1<<(i-1))) When , We only
Modify(1,l,r,i);
among $$Modify$$ Parameters in $$i$$ It's a number .
Get into $$Modify$$ function , Here we use a very common conclusion , For a binary string like ：
$$1\ \ \ 0\ \ \ 1\ \ \ 1\ \ \ 1\ \ \ 0\ \ \ 1$$
He now has $$5$$ individual $$1$$, But if I take them all or one $$1$$ after ：
$$1xor1=0\ \ \ 0xor1=1\ \ \ 1xor1=0\ \ \ 1xor1=0\ \ \ 1xor1=0\ \ \ 0xor1=1\ \ \ 1xor1=0$$
Found no , Just the opposite , So in $$Modify$$ In the function , If $$l==r$$, That is, we need to update this $$sum$$ 了 , This is the time $$t[u][k].sum=(t[u][k].r-t[u][k].l+1)-t[u][k].sum;$$, It's just the opposite .
Another important point is that of this topic $$pushdown$$ function , In fact, it is against his children ：

void pushdown(int u,int k)
{
if(t[u][k].tag)
{
t[u*2][k].tag+=t[u][k].tag;
t[u*2+1][k].tag+=t[u][k].tag;
//		t[u][k].tag=0;
if(t[u][k].tag&1)
{
t[u*2][k].sum=(t[u*2][k].r-t[u*2][k].l+1)-t[u*2][k].sum;
t[u*2+1][k].sum=(t[u*2+1][k].r-t[u*2+1][k].l+1)-t[u*2+1][k].sum;
}
t[u][k].tag=0;
}
}


$$Modify$$ After that, it's $$query$$ Part of , I have to remind you of this problem $$query$$ yes $$1$$ operation , It's the reverse .
$$query$$ Obviously we need to put $$21$$ All binary bits are calculated , That is, every time I return, it's $$t[u][k].sum<<(k-1)$$.
Add up the results in each cycle .

## $$AC$$ Code

//Writer: Dijkstra6627
//Finished Time: May 4th, 2021
//Time Used: 1372 millisecond, 2638 to Time Limit
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=25;
struct XorSegTree
{
int l,r;
long long sum,tag;
}t[N<<2][M];
int n,q,a[N];
long long ans,ans2;
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
void BuildTree(int u,int l,int r)
{
for(int i=1;i<=21;i++) t[u][i].l=l,t[u][i].r=r;
if(l==r)
{
for(int i=1;i<=21;i++) if(a[l]&(1<<(i-1))) t[u][i].sum=1;
return ;
}
int mid=(l+r)>>1;
BuildTree(u*2,l,mid);
BuildTree(u*2+1,mid+1,r);
for(int i=1;i<=21;i++) t[u][i].sum=t[u*2][i].sum+t[u*2+1][i].sum;
}
void pushdown(int u,int k)
{
if(t[u][k].tag)
{
t[u*2][k].tag+=t[u][k].tag;
t[u*2+1][k].tag+=t[u][k].tag;
//		t[u][k].tag=0;
if(t[u][k].tag&1)
{
t[u*2][k].sum=(t[u*2][k].r-t[u*2][k].l+1)-t[u*2][k].sum;
t[u*2+1][k].sum=(t[u*2+1][k].r-t[u*2+1][k].l+1)-t[u*2+1][k].sum;
}
t[u][k].tag=0;
}
}
void Modify(int u,int l,int r,int k)
{
if(l<=t[u][k].l && t[u][k].r<=r)
{
t[u][k].sum=(t[u][k].r-t[u][k].l+1)-t[u][k].sum;
t[u][k].tag++;
return ;
}
pushdown(u,k);
int mid=(t[u][k].l+t[u][k].r)>>1;
if(l<=mid) Modify(u*2,l,r,k);
if(mid<r) Modify(u*2+1,l,r,k);
t[u][k].sum=t[u*2][k].sum+t[u*2+1][k].sum;
}
void query(int u,int l,int r,int k)
{
if(l<=t[u][k].l && t[u][k].r<=r) {ans+=t[u][k].sum<<(k-1);return ;
}
pushdown(u,k);
int mid=(t[u][k].l+t[u][k].r)>>1;
//	int res=0;
if(l<=mid) query(u*2,l,r,k);
if(mid<r) query(u*2+1,l,r,k);
t[u][k].sum=t[u*2][k].sum+t[u*2+1][k].sum;
//	return res;
}
int main()
{
BuildTree(1,1,n);
while(q--)
{
if(op==2)
{
for(int i=1;1<<(i-1)<=x;i++) if(x&(1<<(i-1))) Modify(1,l,r,i);
}
else
{
ans=0;
for(int i=1;i<=21;i++)
{
ans2=0;
query(1,l,r,i);
ans+=ans2;
}
cout<<ans<<endl;
}
}
return 0;
}


## Thank you for reading , Don't forget to like it ！

https://chowdera.com/2021/05/20210504140925249p.html