Codeforces 341D. Iahub and Xors http://codeforces.com/problemset/problem/341/D 2D树状数组

CF341D.cpp

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int maxn = 1031;

int n, m, op, x1, y1, x2, y2;
long long value, tree[2][2][maxn][maxn];

void add(int x, int y, long long val) {
	for (int i = x; i < maxn; i += i & (-i)) {
		for (int j = y; j < maxn; j += j & (-j))
			tree[x&1][y&1][i][j] ^= val;
	}
}

long long query(int x, int y) {
	long long res = 0;
	for (int i = x; i > 0; i -= i & (-i)) {
		for (int j = y; j > 0; j -= j & (-j))
			res ^= tree[x&1][y&1][i][j];
	}
	return res;
}

int main() {
	cin >> n >> m;
	for (int cas = 1; cas <= m; cas++) {
		cin >> op >> x1 >> y1 >> x2 >> y2;
		if (op == 2) {
			cin >> value;
			add(x1, y1, value);
			add(x1, y2 + 1, value);
			add(x2 + 1, y1, value);
			add(x2 + 1, y2 + 1, value);
		} else {
			long long res = query(x1 - 1, y1 - 1);
			res ^= query(x1 - 1, y2);
			res ^= query(x2, y1 - 1);
			res ^= query(x2, y2);
			cout << res << endl;
		}
	}
	return 0;
}