Codeforces #571 Div2 E. Vus the Cossack and a Field

この回は不参加。
https://codeforces.com/contest/1186/problem/E

問題

01で構成されるグリッドを以下のように作る。
まず最小構成としてH*Wの構成が与えられる。これはグリッドの左上に位置する。

以降、以下の手順を繰り返し4倍化を行う。

• 現状のグリッドの右に、同サイズで01反転したものを連結する。
• さらにその状態のグリッドの下に、同サイズで01反転したものを連結する。

こうしたグリッドにおいて、矩形範囲が指定されたとき、範囲内の値の総和を求めよ。

解法

定番として左上を1つの端点とする矩形範囲内の値の総和をO(1)で求められれば良い。

ここで、グリッドの構成法からして以下のことがわかる。

• グリッドを2H*2Wずつに区切った場合、その全体、もしくは1か所辺に平行なラインで区切った範囲は、0,1が同数になる

よって、例えば(1,1)-(h,w)の範囲の値の総和を取るとき、h以下で最大の2Hの倍数をh'、w以下で最大の2Wの倍数をw'とすると、(1,1)-(h',w')、(h'+1,1)-(h,w')、(1,w'+1)-(h',w)の範囲はその半分が1であるため高速に値の総和が取れる。
あとは(h'+1,w'+1)-(h,w)の間の総和を取ればよいが、これは2H*2Wの範囲だけ累積和を取っておけば、高速に範囲内の総和を計算できる。

int H,W,Q;
int A[2049][2049][2];
string S[2048];

ll hoge(ll x,ll y) {
	if(x<=0 || y<=0) return 0;
	ll dx=x/W*W;
	ll dy=y/H*H;
	
	int ind=(__builtin_popcount(x/W)+__builtin_popcount(y/H))%2;
	return x*dy/2+y*dx/2-dx*dy/2+A[y%H][x%W][ind];
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W>>Q;
	FOR(y,H) {
		cin>>S[y];
		FOR(x,W) S[y].push_back(S[y][x]^1);
		FOR(x,2*W) S[y+H].push_back(S[y][x]^1);
	}
	H*=2;
	W*=2;
	FOR(y,H) FOR(x,W) FOR(i,2) A[y+1][x+1][i]=A[y][x+1][i]+A[y+1][x][i]-A[y][x][i]+(S[y][x]==('1'^i));
		
	
	while(Q--) {
		int x1,y1,x2,y2;
		cin>>x1>>y1>>x2>>y2;
		x1--,y1--;
		
		cout<<hoge(y2,x2)-hoge(y1,x2)-hoge(y2,x1)+hoge(y1,x1)<<endl;
		
	}
}

まとめ

反転のさせ方を0/1反転と左右反転で変な勘違いした。