Good Bye 2015 : C. New Year and Domino

今年もよろしくお願いします。
http://codeforces.com/contest/611/problem/C

問題

H*Wのグリッドがあり、埋まったマスと埋まってないマスで構成されている。
ここでQ個のクエリが与えられる。
各クエリはグリッド上の矩形の範囲を示している。
その範囲内で、1*2のドミノを1個置く時、その置き方が何通りあるか答えよ。

解法

前処理しておいて、各クエリO(1)で処理していく。

あるマスについて、そのマスと右隣が空いているか、また下隣が空いているかをそれぞれ求める。
またそれらをそれぞれ2次元の累積和を求めておく。
クエリが(r1,c1)-(r2,c2)の時、(r1,c1)-(r2,c2-1)における右隣マスが空いているマスの数と、(r1,c1)-(r2-1,c2)における下隣マスが空いているマスの数をそれぞれ数え上げればよい。

int H,W,Q;
string S[505];
int ri[505][505];
int down[505][505];
int R[505][505];
int D[505][505];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	FOR(y,H) cin>>S[y];
	FOR(y,H) FOR(x,W-1) if(S[y][x]=='.' && S[y][x+1]=='.') ri[y][x]=1;
	FOR(x,W) FOR(y,H-1) if(S[y][x]=='.' && S[y+1][x]=='.') down[y][x]=1;
	for(y=1;y<=502;y++) {
		for(x=1;x<=502;x++) {
			R[y][x] = R[y-1][x]+R[y][x-1]-R[y-1][x-1]+ri[y-1][x-1];
			D[y][x] = D[y-1][x]+D[y][x-1]-D[y-1][x-1]+down[y-1][x-1];
		}
	}
	
	cin>>Q;
	while(Q--) {
		int x1,x2,y1,y2;
		cin>>y1>>x1>>y2>>x2;
		
		int sum=0;
		sum += R[y2][x2-1]-R[y1-1][x2-1]-R[y2][x1-1]+R[y1-1][x1-1];
		sum += D[y2-1][x2]-D[y1-1][x2]-D[y2-1][x1-1]+D[y1-1][x1-1];
		cout<<sum<<endl;
	}
}

まとめ

ここまでは順調だった。