题解 CF341D 【Iahub and Xors】

1 minute read

Published:

前置知识：二维树状数组(区间修改，区间查询)

二维树状数组例题：上帝造题的七分钟

若已过上述例题，则本题可视为水题通过。

若未过上述例题，则本题解介绍一下异或意义下的二维树状数组。

类似于普通二维树状数组，我们先定义一个异或意义下的差分: $d[i][j]=a[i][j]$^$a[i-1][j]$^$a[i][j-1]$^$a[i-1][j-1]$ ($a[i][j]$原矩阵内的数)。再重定义求和符号 :$\displaystyle \sum_{i=1}^x \sum_{j=1}^y d[i][j]=d[1][1]$^$d[1][2]$^…^$d[1][y]$ ^$d[2][1]$^$d[2][2]$…^$d[2][n]$ ……$d[n][1]$^$d[n][2]$^…$d[n][n]$ 。(以下所有的求和符号皆为重定义后的意义)定义 a ** b 表示b^b^b…^b (b自异或a次)。显然，自异或奇次为自己，自异或偶次为0 。

那么，$\displaystyle a[x][y]=\sum_{i=1}^x \sum_{j=1}^y d[i][j]$。证明：

因为$d[i][j]=a[i][j]$ ^ $a[i-1][j]$^$a[i][j-1]$ ^ $a[i-1][j-1]$.

所以 $a[x][y]=$ $\displaystyle \sum_{i=1}^x \sum_{j=1}^y a[i][j]$ ^ $ \displaystyle\sum_{i=1}^{x-1} \sum_{j=1}^y a[i][j]$ ^ $ \displaystyle\sum_{i=1}^x \sum_{j=1}^{y-1} a[i][j]$ ^ $\displaystyle\sum_{i=1}^{x-1} \sum_{j=1}^{y-1} a[i][j]$ 。

定义前缀和, $s[x][y]=\displaystyle \sum_{i=1}^x \sum_{j=1}^y a[i][j]$ 。

我们将 $\displaystyle a[x][y]=\sum_{i=1}^x \sum_{j=1}^y d[i][j]$ 带入得 $s[x][y]=$ $\displaystyle [(x+1) * (y+1)] $ ** $ \sum_{i=1}^x \sum_{j=1}^y d[i][j]$ ^ $\displaystyle (y+1) $ ** $ \sum_{i=1}^x \sum_{j=1}^y i $ ** $ d[i][j]$ ^ $\displaystyle (x+1) $ ** $\sum_{i=1}^x \sum_{j=1}^y j $ ** $ d[i][j]$ ^ $\displaystyle \sum_{i=1}^x \sum_{j=1}^y (i * j)$ ** $d[i][j]$ 。

开4颗树状数组维护 $d[i][j]$ , $i $ ** $ d[i][j]$ , $j $ ** $ d[i][j],(i * j) $ ** $ d[i][j]$ 这四个值。（注意：在树状数组中，加号被重定义为 ^ 号）。

(以下符号与原题无关，仅与重定义后的树状数组有关)

这里阐述一下树状数组所维护的东西: 对于定义在此树状数组下的矩阵 $v$ ，其各值分别为 $v[i][j]$,我们使用树状数组 $w[i][j]$ 维护其前缀异或和.对于一次询问$ask(x,y)$，我们的返回值 $\displaystyle ask(x,y)=\sum_{i=1}^x \sum_{j=1}^y v[i][j]$ ，即将 $(x,y)$ 在树状数组中的管辖范围内的所有 $w[i][j]$ 异或和。对于此树状数组下的一次修改”$add(x,y,k)$(即$v[x][y]->v[x][y]$^$k$)”，我们修改了所有包含 $(x,y)$ 的 $w[i][j]$ 值，使其异或 $k$ .

我们在原题中需要用此重定义的树状数组维护4个不同矩阵 $d[i][j]$ , $i $ ** $ d[i][j]$ , $j $ ** $ d[i][j],(i * j) $ ** $ d[i][j]$ 的前缀异或和。

时间复杂度 $O(mlog^2n)$。

#include<bits/stdc++.h>
#define ll long long
#define dl double
#define re register
#define LL inline ll
#define I inline int
#define V inline void
#define gc getchar()
#define FOR(i,a,b) for(re int i=(a) , i##i=(b) ; i<=i##i ; ++i)
#define ROF(i,a,b) for(re int i=(a) , i##i=(b) ; i>=i##i ; --i)
using namespace std;
const int N=1050;
LL read(){
	ll p=0,w=0;
	char ch=gc;
	while(!isdigit(ch)) w=ch=='-'?1:0,ch=gc;
	while(isdigit(ch)) p=p*10+ch-'0',ch=gc;
	return w?-p:p;
}
ll n,m,d[N][N];
struct ao{
	ll s[N][N];
	I lowbit(int x){ return x&(-x);}
	V add(int x,int y,ll k){
		if(!x||!y||!k) return ;
		for(re int i=x;i<=n;i+=lowbit(i))
			for(re int j=y;j<=n;j+=lowbit(j))
				s[i][j]^=k;
	}
	LL ask(int x,int y){
		ll as=0;
		for(re int i=x;i;i-=lowbit(i))
			for(re int j=y;j;j-=lowbit(j))
				as^=s[i][j];
		return as;
	}
}a,ai,aj,aij;
V add(int x,int y,ll k){ a.add(x,y,k),ai.add(x,y,k*(x&1)),aj.add(x,y,k*(y&1)),aij.add(x,y,k*(x*y&1));}
V add(int x1,int y1,int x2,int y2,ll k){ add(x1,y1,k),add(x2+1,y1,k),add(x1,y2+1,k),add(x2+1,y2+1,k);}
LL ask(int x,int y){ return ((x+1)*(y+1)&1)*a.ask(x,y)^((y+1)&1)*ai.ask(x,y)^((x+1)&1)*aj.ask(x,y)^aij.ask(x,y); }
LL ask(int x1,int y1,int x2,int y2){ return ask(x2,y2)^ask(x2,y1-1)^ask(x1-1,y2)^ask(x1-1,y1-1); }
int main (){
	int cz,x1,y1,x2,y2,k;
	n=read(),m=read();
	FOR(i,1,m){
		cz=read();
		if(cz==2) x1=read(),y1=read(),x2=read(),y2=read(),k=read(),add(x1,y1,x2,y2,k);
		else x1=read(),y1=read(),x2=read(),y2=read(),printf("%d\n",ask(x1,y1,x2,y2));
	}
	return 0;
}

You May Also Enjoy