2215 Parliament

問題概要

R行S列の行列が与えられる。
この行列のR1行S1列からR2行S2列までの長方形の部分の成分の和を求めよ。


行列の各成分はintに収まる範囲であり、R,S≦1000を満たす。

解法

i行j列目までの和をs[i][j]などとして持っておけば、
長方形の和はO(1)で計算できる。

ソースコード

int w,h,a[1000][1000];
ll s[1001][1001];

int main(){
	int T; scanf("%d",&T);
	rep(U,T){
		scanf("%d%d",&h,&w);
		rep(i,h)rep(j,w){
			scanf("%d",a[i]+j);
			s[i+1][j+1]=a[i][j]+s[i+1][j]+s[i][j+1]-s[i][j];
		}
		int q,x1,x2,y1,y2;
		scanf("%d",&q);
		rep(i,q){
			scanf("%d%d%d%d",&y1,&x1,&y2,&x2); x1--; y1--;
			ll ans=s[y2][x2]+s[y1][x1]-s[y2][x1]-s[y1][x2];
			printf("Absolutni hodnota pohodlnosti je %lld bodu.\n",ans);
		}
		puts("");
	}
	return 0;
}