Codeforces #198 Div1 D. Iahub and Xors

理解してしまえばコードは単純。
http://codeforces.com/contest/341/problem/D

問題

N次正方行列A[i]が与えられる。
ここに対し以下のクエリM個を処理せよ。

1. 部分行列の位置(x1,y1)-(x2,y2)が指定されるので、それらの各要素のxorを取った値を返す。
2. 部分行列の位置(x1,y1)-(x2,y2)が指定されるので、各要素をvでxor取った値で更新する。

解法

まずxorではなく通常の足し算で行うことを考える。
この場合は、２次元BITを使うと更新・和の取得が２次元累積和の更新の要領で１回O((logN)^2)で行える。
例えば和の取得は(0,0)-(x2,y2)の和から(0,0)-(x1-1,y2)と(0,0)-(x2,y1-1)の和を引き、(0,0)-(x1-1,y1-1)の和を足せばよい。
vを加える場合はBIT中で(x2,y2)と(x1-1,y1-1)にvを足し、(x1-1,y2)と(x2,y1-1)にvを足せばよい。

次にこの手順を足し算ではなくxorで行う場合を考える。
ある行に注目した場合、たとえば更新クエリでA[i][j]～A[i][j+k]にvをxorで足しこんだとする。
次に値の取得クエリがA[i][j]～A[i][j+k]を含んでいる場合、奇数個含んでいるならv、偶数個含んでいるなら0最終的な結果に反映される。

この条件より、BITをxの偶奇およびyの偶奇ごと計4つ作り、値の更新・取得はそれぞれ対応するBITに対して行うようにすればよい。

int N,M;

template<class V,int MA> class BIT_2d {
public:
	V val[1<<MA][1<<MA];
	BIT_2d(){ZERO(val);};
	V total(int x,int y) {
		V s=0;
		for(int i=x+1;i>0;i-=i&-i) for(int j=y+1;j>0;j-=j&-j) s^=val[i-1][j-1];
		return s;
	}
	void update(int x,int y,ll v) {
		for(int i=x+1;i<=1<<MA;i+=i&-i) for(int j=y+1;j<=1<<MA;j+=j&-j) val[i-1][j-1]^=v;
	}
};
BIT_2d<ll,10> bit[2][2];

void solve() {
	int i,j,k,l,r,x1,y1,x2,y2; string s;
	ll v;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>j>>x1>>y1>>x2>>y2;
		if(j==1) {
			ll ret=0;
			ret ^= bit[x2%2][y2%2].total(x2,y2);
			ret ^= bit[x2%2][(y1-1)%2].total(x2,y1-1);
			ret ^= bit[(x1-1)%2][y2%2].total(x1-1,y2);
			ret ^= bit[(x1-1)%2][(y1-1)%2].total(x1-1,y1-1);
			cout<<ret<<endl;
		}
		if(j==2) {
			cin>>v;
			bit[x1%2][y1%2].update(x1,y1,v);
			bit[(x2+1)%2][y1%2].update(x2+1,y1,v);
			bit[x1%2][(y2+1)%2].update(x1,y2+1,v);
			bit[(x2+1)%2][(y2+1)%2].update(x2+1,y2+1,v);
		}
	}
	
}

まとめ

BITを４つ使うことに気が付けばあとはすぐ。
でも気づくのが難しいね。