CF 242E(zkw线段树-拆位）

Posted on by
内容目录
E. XOR on Segment
time limit per test

4 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

对于数组，a1, a2, ..., an.
请维护2个操作。

  1. 区间[l, r], 求和.
  2. 将区间 [l, r],上的数异或x
Input

第一行为数组大小 n (1 ≤ n ≤ 105), 第二行为数组 a1, a2, ..., an(0 ≤ ai ≤ 106) 

第三行为操作数 m (1 ≤ m ≤ 5·104),接下来每行第1个数ti (1 ≤ ti ≤ 2)
表示进行第i种操作. ‘1
li, ri ‘(1 ≤ li ≤ ri ≤ n)表示[l,r]求和.‘2 li, ri, xi (1 ≤ li ≤ ri ≤ n, 1 ≤ xi ≤ 106)表示将区间 [l, r],上的数异或x

Output

输出所有操作1的结果。

不要用%lld 占位符，改用输入输出流或%I64占位符.

Sample test(s)
input
5
4 10 3 13 7
8
1 2 4
2 1 3 3
1 2 4
1 3 3
2 2 5 5
1 1 5
2 1 2 10
1 2 3
output
26
22
0
34
11
input
6
4 7 4 0 7 3
5
2 2 3 8
1 1 5
2 3 5 1
2 4 5 6
1 2 3
output
38
28

这题是xor拆位法的运用

显然我们可以用t[i,j]表示第i位上的1的个数，之后求和统计（这是xor操作优化的常用手段）

zkw线段树加Lazy标记时，用tot[]表示区间上的总数(其实也可以时事算出来）


#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<cctype>
#include<iostream>
using namespace std;
#define MAXN (100000+10)
#define MAXAi (1000000+10)
#define LogMAXAi (20)
#define MAXm (50000)
#define NDEBUG
int n,m,M,t[LogMAXAi+10][MAXN*10],tot[MAXN*10]={0};
bool b[LogMAXAi+10][MAXN*10]={0};
void build_tree()
{
	for (int i=M+1;i<=M+n;i++) tot[i]=1;
	for (int i=M-1;i>=1;i--) tot[i]=tot[i<<1]+tot[(i<<1)^1];

}
long long count_a_tree_node(int x)
{
	long long ans=0;
	for (int i=0,p=1;i<20;i++,p<<=1) ans+=(long long)(p)*(long long)(t[i][x]);
	return ans;
}
long long quere(int l,int r)
{
	long long ans=0;
	l--;r++;
	l+=M;r+=M;
	while (l^r^1)
	{
		if (~l&1) ans+=count_a_tree_node(l+1);
		if (r&1) ans+=count_a_tree_node(r-1);
		l>>=1;r>>=1;
	}
	return ans;
}
void pushdown(int x)
{
	if (x!=1) pushdown(x>>1);
	for (int i=0;i<20;i++)
	{
		if (b[i][x])
		{
			t[i][x<<1]=tot[x<<1]-t[i][x<<1];
			t[i][(x<<1)^1]=tot[(x<<1)^1]-t[i][(x<<1)^1];
			b[i][x]=0;b[i][x<<1]^=1;b[i][(x<<1)^1]^=1;
		}
	}
}
void update(int x)
{
	for (int i=0;i<20;i++)
	{
		int xx=x;
		for (x>>=1;x;x>>=1)
			t[i][x]=t[i][x<<1]+t[i][(x<<1)^1];
		x=xx;
	}
}
void a_t_xor(int j,int l,int r)
{
	l--;r++;
	l+=M;r+=M;
	while (l^r^1)
	{
		if (~l&1) {t[j][l+1]=tot[l+1]-t[j][l+1];b[j][l+1]^=1;	}
		if (r&1) {t[j][r-1]=tot[r-1]-t[j][r-1];b[j][r-1]^=1;	}
		l>>=1;r>>=1;
	}
}
void t_xor(int l,int r,int x)
{
	for (int i=0;x;i++,x>>=1) {if (x&1) a_t_xor(i,l,r);	}
}
int main()
{
//	freopen("CF_242E.in","r",stdin);
	memset(t,0,sizeof(t));
	scanf("%d",&n);
	M=1;while (M-2<n) M<<=1; //cout<<M<<endl;
	for (int i=M+1;i<=M+n;i++)
	{
		scanf("%d",&t[0][i]);
		int j=0;
		while (t[j][i]) {t[j+1][i]=t[j][i]/2;t[j][i]&=1;j++;}
	}
	for (int j=0;j<=19;j++)
	{
		for (int i=M-1;i>=1;i--) t[j][i]=t[j][i<<1]+t[j][(i<<1)^1];
	}
	#ifndef NDEBUG
	for (int i=1;i<=M+n;i++)
	{
		for (int j=0;j<=19;j++) cout<<t[j][i]<<' ';
		cout<<endl;
	}
	#endif
	build_tree();
	/*
	for (int i=1;i<=M+n;i++) cout<<tot[i]<<' ';
	cout<<endl;
	*/
	scanf("%d",&m);
	while (m)
	{
		int p;
		scanf("%d",&p);
		if (p==1)
		{
			int l,r;scanf("%d%d",&l,&r);
			pushdown(l-1+M);pushdown(r+1+M);
			cout<<quere(l,r)<<endl;
		}
		else
		{
			int l,r,x;
			scanf("%d%d%d",&l,&r,&x);
			pushdown(l-1+M);pushdown(r+1+M);
			t_xor(l,r,x);
			update(l-1+M);update(r+1+M);
		}

		#ifndef	NDEBUG
		for (int i=1;i<=M+n;i++)
		{
			for (int j=0;j<=19;j++) cout<<t[j][i]<<' ';
			cout<<endl;
		}
		#endif
		m--;
	}
	return 0;
}