理解してしまえばコードは単純。
http://codeforces.com/contest/341/problem/D
問題
N次正方行列A[i]が与えられる。
ここに対し以下のクエリM個を処理せよ。
- 部分行列の位置(x1,y1)-(x2,y2)が指定されるので、それらの各要素のxorを取った値を返す。
- 部分行列の位置(x1,y1)-(x2,y2)が指定されるので、各要素をvでxor取った値で更新する。
解法
まずxorではなく通常の足し算で行うことを考える。
この場合は、2次元BITを使うと更新・和の取得が2次元累積和の更新の要領で1回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を4つ使うことに気が付けばあとはすぐ。
でも気づくのが難しいね。