[TIOJ] 1991. 冰塊盒

題目連結:http://tioj.infor.org/problems/1991

---

大概看個一兩眼就會發現其實橫的跟直的可以分開，每個區塊都是獨立的(表示我選了這塊，我再選另一塊並不會影響前面那塊的值(某些奇怪的題目會有))，所以不難發現實作個二維的前綴和就好了，跟普通前綴和差不多，就輸出的時候再扣掉不要的部分就好了。

#include <bits/stdc++.h>
using namespace std;
const int N = 2000000 + 5;
#define Hash(i, j) ((i)*(m+1)+(j))

bool mtx[N];
int preH[N], preZ[N];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n, m; cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>mtx[Hash(i, j)];
			if(mtx[Hash(i, j)] and mtx[Hash(i, j-1)]) preH[Hash(i, j)]++;
			if(mtx[Hash(i, j)] and mtx[Hash(i-1, j)]) preZ[Hash(i, j)]++;
			preH[Hash(i, j)]+=preH[Hash(i, j-1)];
			preZ[Hash(i, j)]+=preZ[Hash(i-1, j)];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			preH[Hash(i, j)]+=preH[Hash(i-1, j)];
			preZ[Hash(i, j)]+=preZ[Hash(i, j-1)];
		}
	}
	int q; cin>>q;
	while(q--){
		int x1, y1, x2, y2; cin>>x1>>y1>>x2>>y2;
		cout<<(preZ[Hash(x2, y2)]+preZ[Hash(x1, y1-1)]-preZ[Hash(x1, y2)]-preZ[Hash(x2, y1-1)] + \
			preH[Hash(x2, y2)]+preH[Hash(x1-1, y1)]-preH[Hash(x1-1, y2)]-preH[Hash(x2, y1)])<<'\n';
	}
	return 0;
}