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

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

求和式 (C++ 坑爹的<<,>>,%lld)

求和式(x3)

题目描述

作为本场考试的第一题,你的任务十分简单:

给定长度为n的序列A[i],求所有A[i]xor A[j] (i<j)的值之和

 

输入

第一行一个整数N

接下来N行,第i行为A[i]

输出

所需的值

 

样例输入

3

7

3

5

样例输出

12

样例解释

7 xor 3+3 xor 5+7 xor 5 = 4+6+2 = 12

 

数据范围

对于40%的数据,N<=5000

对于100%的数据,N<=1000000

c++中的%lld千万别用啊 ,各种坑人!

统一用cout 

另外C++中(long long)(1<<k)

这里要转,不然必wa

千万要先乘,和别的数乘完不定什么数了……

本题是位运算分解成一位一位运算(重要性质)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (100+10)
int n,a,c[MAXN][2]={0};// 1<<i =(0.1)
int main()
{
	freopen("x3.in","r",stdin);
	freopen("x3.out","w",stdout);

/*	for (int i=0;i<=100;i++)
	{
		cout<<c[i][0]<<' '<<c[i][1]<<endl;
	}
*/	long long ans=0;
	scanf("%d",&n);
	int len=0;
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&a);
		int tot=-1;
		int j=100;
		while (j--) {c[++tot][a%2]++;a/=2;}



		len=len<tot?tot:len;

	}
/*	for (int i=0;i<=100;i++)
	{
		cout<<c[i][0]<<' '<<c[i][1]<<endl;
	}
*/
	for (int i=0;i<=28;i++)
	{
		ans+=(long long)(1<<i)*(long long)c[i][1]*(long long)(n-c[i][1]);

//	cout<<ans<<endl;
	}


/*
	for (int i=0;i<=len;i++) cout<<c[i][0]<<' '<<c[i][1]<<' '<<endl;
*/

//	printf("%lldn",ans);
	cout<<ans<<endl;
//	while (1);

	return 0;
}



POJ 3748(C++的16进制读法 %x)

P党写几小时的程序 C++才几行……

首先P的位运算有上限2^30 此时 即便是 int64也会因为补码坑死人的

到1 shl 31时   int64 是负数 故 这个时候 不能shr 为多出好多位

造成以上结果的真正原因是 shl 和 shr 只支持到1 shl 30 (Longint)所以在int64或qword会出错 要自己写


C党读入方法 %x 表示 二进制

#include<cstdio>
using namespace std;
int r,x,y;
int main()
{
	scanf("%x,%d,%d",&r,&x,&y);
	r=r&(~(1<<x));
	r=r&(~(1<<y-2));
	r=r|(1<<(y-1))|(1<<(y));
	printf("%xn",r);


}

P党取到30的做法:

Program P3748;
const
// ordA=65;
   orda=97;
   ord0=48;
var
   s:string;
   r:qword;
   x,y:longint;
function turn2(c:char):longint;
begin
   if ord(c)>=orda then begin exit(ord(c)-orda+10); end
   else exit(ord(c)-ord0);
end;
function turn16(x:qword):longint;
begin
   if (x<>0) then
   begin
      turn16:=x and 15;
      x:=x shr 4;
      turn16(x);
      if turn16<=10 then write(turn16) else write(chr(turn16-10+orda));
   end;
end;
function cin:longint;
var
   i:longint;
   s1:string;
begin
   i:=1;
   while s[i]<>',' do inc(i);
   s1:=copy(s,1,i-1);
   val(s1,cin);
   delete(s,1,i);


end;

function cin16:qword;
var
   i,j:longint;
   s1:string;
begin
   i:=1;
   while s[i]<>',' do inc(i);
   s1:=copy(s,1,i-1);
   cin16:=0;
   for j:=1 to i-1 do
      cin16:=cin16 shl 4+turn2(s1[j]);
   delete(s,1,i);
end;


begin
   readln(s);
   r:=cin16;x:=cin;val(s,y);


   r:=r and (not (1 shl x));

   r:=r and (not (1 shl (y-2)));
   r:=r or (1 shl (y-1));
   r:=r or (1 shl y);
   turn16(r);
   writeln;

end.

更正AC版:

Program P3748;
const
// ordA=65;
   orda=97;
   ord0=48;
var
   s:string;
   r,k:qword;
   x,y,i:longint;
function turn2(c:char):longint;
begin
   if ord(c)>=orda then begin exit(ord(c)-orda+10); end
   else exit(ord(c)-ord0);
end;
function turn16(x:qword):longint;
begin
   if (x<>0) then
   begin
      turn16:=x and 15;
      x:=x div 16;
      turn16(x);
      if turn16<=10 then write(turn16) else write(chr(turn16-10+orda));
   end;
end;
function cin:longint;
var
   i:longint;
   s1:string;
begin
   i:=1;
   while s[i]<>',' do inc(i);
   s1:=copy(s,1,i-1);
   val(s1,cin);
   delete(s,1,i);
end;
function cin16:qword;
var
   i,j:longint;
   s1:string;
begin
   i:=1;
   while s[i]<>',' do inc(i);
   s1:=copy(s,1,i-1);
   cin16:=0;
   for j:=1 to i-1 do
      cin16:=cin16 shl 4+turn2(s1[j]);
   delete(s,1,i);
end;

function shl2(x:longint):qword;
var
   i:longint;
begin
   shl2:=1;
   for i:=1 to x do shl2:=shl2*2;

end;
begin
   readln(s);
   r:=cin16;x:=cin;val(s,y);


  r:=r and (not (shl2(x)));


   r:=r and (not (shl2(y-2)));

   r:=r or (shl2(y-1));
   r:=r or (shl2(y));
   turn16(r);
   writeln;

end.

附:

    功能              |           示例            |    位运算
----------------------+---------------------------+--------------------
去掉最后一位          | (101101->10110)           | x shr 1
在最后加一个0         | (101101->1011010)         | x shl 1
在最后加一个1         | (101101->1011011)         | x shl 1+1
把最后一位变成1       | (101100->101101)          | x or 1
把最后一位变成0       | (101101->101100)          | x or 1-1
最后一位取反          | (101101->101100)          | x xor 1
把右数第k位变成1      | (101001->101101,k=3)      | x or (1 shl (k-1))
把右数第k位变成0      | (101101->101001,k=3)      | x and not (1 shl (k-1))
右数第k位取反         | (101001->101101,k=3)      | x xor (1 shl (k-1))
取末三位              | (1101101->101)            | x and 7
取末k位               | (1101101->1101,k=5)       | x and (1 shl k-1)
取右数第k位           | (1101101->1,k=4)          | x shr (k-1) and 1
把末k位变成1          | (101001->101111,k=4)      | x or (1 shl k-1)
末k位取反             | (101001->100110,k=4)      | x xor (1 shl k-1)
把右边连续的1变成0    | (100101111->100100000)    | x and (x+1)
把右起第一个0变成1    | (100101111->100111111)    | x or (x+1)
把右边连续的0变成1    | (11011000->11011111)      | x or (x-1)
取右边连续的1         | (100101111->1111)         | (x xor (x+1)) shr 1
去掉右起第一个1的左边 | (100101000->1000)         | x and (x xor (x-1))