「CF242E」XOR on Segment 解题报告

题面

长度为\(n\)的数列，现有两种操作：

1、区间异或操作

2、区间求和操作

对于每个查询，输出答案

思路：

线段树+二进制拆位

线段树区间修改一般使用的都是懒标记的方法，但是对于异或，懒标记的方法显然是行不通的，于是就考虑二进制拆位

主要的思路就是将一个数，拆成若干个二进制位，然后对于异或操作，就转换成了每一位上的异或操作

分类讨论一下：

1、当\(x\)的第\(i\)位为\(1\)时，\(1\ xor\ 0=1\)，\(1\ xor\ 1=0\)

也就是看成区间取反操作

2、当\(x\)的第\(i\)位为\(0\)时，\(0\ xor\ 0=0\)，\(0\ xor\ 1=1\)

也就是说操作前后没有变化，所以就不执行修改操作

Code：

#include<bits/stdc++.h>

#define ll long long

#define N 100010

using namespace std;

int n,a[N],res,L,R,T,x;

int f[N<<2][25],tag[N<<2][25];//1e6<2^20

ll b[25],ans;//别忘记long long

int read(){ int s=0;char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)){s=(s<<1)+(s<<3)+c-'0';c=getchar();}

    return s;

}

void built(int k,int l,int r)

{

	if(l>r) return;

	if(l==r)

	{

		res=a[l];

		for(int i=0;i<21;i++)//拆位

			if((res>>i)&1) f[k][i]=1;

		return;

	}

	int mid=(l+r)>>1,cur=k<<1;

	built(cur,l,mid);

	built(cur|1,mid+1,r);

	for(int i=0;i<21;i++)

		f[k][i]=f[cur][i]+f[cur|1][i];

	return;

}

void push(int k,int l,int r,int p)//p表示第几位

{

	f[k][p]=(r-l+1)-f[k][p];//区间取反

	if(l!=r)

	{

		int cur=k<<1;

		tag[cur][p]^=1;

		tag[cur|1][p]^=1;

	}

	tag[k][p]=0;

}

void Modify(int k,int l,int r,int p)//p同上

{

	if(tag[k][p]) push(k,l,r,p);

	if(r<L||R<l) return;

	if(L<=l&&r<=R)

	{

		push(k,l,r,p);

		return;

	}

	int mid=(l+r)>>1,cur=k<<1;

	Modify(cur,l,mid,p);

	Modify(cur|1,mid+1,r,p);

	f[k][p]=f[cur][p]+f[cur|1][p];

}

void Query(int k,int l,int r)//查询，所有位的懒标记都要下放

{

	for(int i=0;i<21;i++)

		if(tag[k][i]) push(k,l,r,i);

	if(r<L||R<l) return;

	if(L<=l&&r<=R)

	{

		for(int i=0;i<21;i++) ans+=f[k][i]*b[i];

		return;

	}

	int mid=(l+r)>>1,cur=k<<1;

	Query(cur,l,mid);

	Query(cur|1,mid+1,r);

}

int main()

{

    int i,j;b[0]=1;

    for(i=1;i<=21;i++) b[i]=b[i-1]<<1;//初不初始化都可以，就是上面b[i]要变成1<<i

    n=read();

    for(i=1;i<=n;i++) a[i]=read();

    built(1,1,n);

    T=read();

    while(T--)

    {

    	if(read()==1)

    	{

    		L=read();R=read();ans=0;

    		Query(1,1,n);

    		printf("%lld\n",ans);

		}

		else

		{

			L=read();R=read();x=read();

			for(i=0;i<21;i++)//判断x的第i位是不是1，并进行修改

				if((x>>i)&1) Modify(1,1,n,i);

		}

	}

    return 0;

}

巴特西

「CF242E」XOR on Segment 解题报告

题面

思路：

线段树+二进制拆位

最新文章

热门文章