当前位置:网站首页>CodeForces CF242E (CodeForces Round 149 Div.2 Problem E)题解

CodeForces CF242E (CodeForces Round 149 Div.2 Problem E)题解

2021-05-04 14:11:03 Dijkstra6627

题意理解

为数不多的\(CodeForces\)上面题意写的较为简洁易懂的题目。
让你维护一个长度为\(n\)的序列,需要支持两种操作,一个是区间异或,即对于任意\(i\in [l,r]\),我们需要将\(a[i]\ xor\ x\)
第二个就是一个基本的区间求和。
数据范围:\(n\le 1e5\)\(m\le 5e4\)\(a[i],x[i]\le 1e6\)

解题思路

本题属于线段树进阶题,对线段树还不太了解的小伙伴们可以先学习一下线段树
异或这个东西很麻烦,因为你不能把他跟加减乘除一样记录\(tag\)然后跑\(lazy-tag\),所以我们要寻找新的出路。其实这道题带来的收获很大,我们考虑一下异或的运算方式,即对于数字\(a\)\(b\)的每一位进行考虑。那么我们能不能根据这个性质照猫画虎呢?
我们发现,题目中给的数据范围是\(10^6\),刚好比\(2^{20}\)小一点点,也就是说,如果我们对每个数字进行二进制拆位的话,只需要\(20\)的空间就够了。所以,我们可以考虑如何用线段树来维护这个东西。我们开\(21\)棵线段树,每一棵线段树都存了这些数的一个二进制位,\(20\)位就可以满足题目的要求。

树确定完了之后我们考虑如何来建树。
针对我们这一群树的性质,显然建树需要一位一位的建。其实就是每次多了一个从\(1\)\(21\)的循环,看起来是这个鸭子的:
for(int i=1;i<=21;i++) t[u][i].l=l,t[u][i].r=r;
如果\(l==r\),即叶子结点,那么我们发现我们就需要这\(21\)棵树都分别划清界限,单独处理自己的那一位,也就是说,如果当前这个\(a[l]\)的第\(k\)位(二进制位)是\(1\),那么直接\(t[u][k].sum=1;\)
之后的\(pushup\)部分也是一样,需要循环\(21\)次。
建树部分代码:

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;
}

建树完成之后我们考虑一下如何进行区间修改。
对于这个题目输入数据提供的,需要被异或的数字\(x\)来说,如果\(x\)的某一个二进制位是\(0\)因为\(0\)异或任何数都是那个数本身,所以可以不用处理。如果某一个二进制位是\(1\),那么显然这个\(1\)要去跟别人发生一遍运算,所以当且仅当:
for(int i=1;1<<(i-1)<=x;i++) if(x&(1<<(i-1)))的时候,我们才
Modify(1,l,r,i);
其中\(Modify\)中的参数\(i\)是位数。
进入\(Modify\)函数,这里我们要使用到一个很常见的结论,对于一个二进制串比如:
\(1\ \ \ 0\ \ \ 1\ \ \ 1\ \ \ 1\ \ \ 0\ \ \ 1\)
他现在有\(5\)\(1\),但是如果我把他们都异或一个\(1\)之后:
\(1xor1=0\ \ \ 0xor1=1\ \ \ 1xor1=0\ \ \ 1xor1=0\ \ \ 1xor1=0\ \ \ 0xor1=1\ \ \ 1xor1=0\)
发现没有,刚好反过来了,所以在\(Modify\)函数里,如果\(l==r\),也就是我们要更新这个\(sum\)了,这个时候\(t[u][k].sum=(t[u][k].r-t[u][k].l+1)-t[u][k].sum;\),也就是刚好反过来。
还有一个重点就是这道题目的\(pushdown\)函数,其实就是对他的子女们取反:

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\)完了之后就是\(query\)的部分,不得不提醒这道题的\(query\)\(1\)操作,是反过来的。
\(query\)的时候显然我们需要把\(21\)个二进制位都计算一遍,即每次返回的时候都是\(t[u][k].sum<<(k-1)\)
每次循环的时候把结果累加即可。

\(AC\)代码

//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;
} 

感谢阅读,别忘点赞哦!

版权声明
本文为[Dijkstra6627]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/juruo-wsy/p/14729327.html

随机推荐