当前位置:网站首页>Codeforces cf242e (codeforces round 149 div.2 problem E)

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

2021-05-04 14:11:59 Dijkstra6627

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
//All Rights Reserved
#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 read()
{
	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()
{
	n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	BuildTree(1,1,n);		
	q=read();
	while(q--)
	{
		int op=read();
		if(op==2)
		{	
			int l=read(),r=read();
			int x=read();
			for(int i=1;1<<(i-1)<=x;i++) if(x&(1<<(i-1))) Modify(1,l,r,i);
		}
		else
		{
			ans=0;
			int l=read(),r=read();
			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 !

版权声明
本文为[Dijkstra6627]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/05/20210504140925249p.html

随机推荐