线段树+二进制位拆分【CF242E】XOR on Segment

Description

给定一个长为\(n(n<=10^5)\)的数组

数组里的数不超过\(10^6\)

有两种操作：

1:求\(sum[l,r]\);

2:对\([l,r]\)中的所有数和\(x\)异或

Input

第一行一个整数\(n\),代表有一个长度为\(n\)的数组。

第二行\(n\)个整数,代表\(a_i\)

第三行为一个整数\(m\),代表有\(m\)次操作。

接下来\(m\)行每行描述一个操作。

Output

对于每一个操作\(1\),输出一行代表\(sum[l,r]\).

这题不错,线段树+二进制拆位

由于异或不具有叠加性,所以不能用\(lazy\)标记直接异或。

我们记录\(tr[o][i]\)代表当前节点\(o\),二进制位\(i\)上是\(1\)的数有多少个。

由于,如果某一二进制位上原来为\(1\),且当前异或的数\(x\),当前二进制位上也有\(1\),那么我们的当前\(tr[o][i]=r-l+1-tr[o][i]\)。

可以理解为\(01\)交换。

然后由于\(2^{20}\)比\(10^6\)要大。

所以只需要拆到\(20\)即可。

然后直接计算即可。

PS：记得开\(long \ long\)！

代码

#include<cstdio>

#include<algorithm>

#include<iostream>

#define int long long

#define R register

using namespace std;

const int gz=1e5+8;

inline void in(R int &x)

{

	R int f=1;x=0;char s=getchar();

	while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}

	while(isdigit(s)){x=x*10+s-'0';s=getchar();}

	x*=f;

}

int n,tr[gz<<2][21],tg[gz<<2],m;

#define ls o<<1

#define rs o<<1|1

inline void up(R int o)

{

	for(R int i=20;~i;i--)

		tr[o][i]=tr[ls][i]+tr[rs][i];

}

void build(R int o,R int l,R int r)

{

	if(l==r)

	{

		R int x;in(x);

		for(R int i=20;~i;i--)

			if((x>>i)&1)tr[o][i]++;

		return;

	}

	R int mid=(l+r)>>1;

	build(ls,l,mid);

	build(rs,mid+1,r);

	up(o);

}

inline void down(R int o,R int l,R int r)

{

	if(tg[o]==0)return;

	tg[ls]^=tg[o];tg[rs]^=tg[o];

	R int mid=(l+r)>>1;

	for(R int i=20;~i;i--)

	{

		if((tg[o]>>i)&1)

			tr[ls][i]=mid-l+1-tr[ls][i],

			tr[rs][i]=r-mid-tr[rs][i];

	}

	tg[o]=0;

	return;

}

void change(R int o,R int l,R int r,R int x,R int y,R int k)

{

	if(x<=l and y>=r)

	{

		tg[o]^=k;

		for(R int i=20;~i;i--)

			if((k>>i)&1)

				tr[o][i]=r-l+1-tr[o][i];

		return;

	}

	down(o,l,r);

	int mid=(l+r)>>1;

	if(x<=mid)change(ls,l,mid,x,y,k);

	if(y>mid) change(rs,mid+1,r,x,y,k);

	up(o);

}

int query(R int o,R int l,R int r,R int x,R int y)

{

	if(x<=l and y>=r)

	{

		R int res=0;

		for(R int i=20;~i;i--)

			res+=(1<<i)*tr[o][i];

		return res;

	}

	down(o,l,r);

	R int mid=(l+r)>>1,as=0;

	if(x<=mid)as+=query(ls,l,mid,x,y);

	if(y>mid)as+=query(rs,mid+1,r,x,y);

	return as;

}

signed main()

{

	in(n);build(1,1,n);in(m);

	for(R int opt,l,r,x;m;m--)

	{

		in(opt);

		if(opt==1)

		{

			in(l),in(r);

			printf("%lld\n",query(1,1,n,l,r));

		}

		else

		{

			in(l),in(r),in(x);

			change(1,1,n,l,r,x);

		}

	}

}

巴特西

线段树+二进制位拆分【CF242E】XOR on Segment

Description

Input

Output

最新文章

热门文章