[TIOJ]1991. 冰塊盒

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

不難發現答案可以利用前綴和來維護，既然是二維的那就用前綴和的前綴和來維護。
一個記放橫的答案，另一個記放直的答案。
因為陣列難先開好，所以把座標Hash掉。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <queue>
#include <vector>
#define lld long long
#define PB push_back
#define F first
#define S second
#define jizz cin.tie(0);ios_base::sync_with_stdio(0);
#define endl '\n'
using namespace std;
typedef pair<int,int> Pair;
int r,c;
bitset<1000006> box;
int a[1000006],b[1000006];
inline int h(int x,int y){
    if(x < 1 || x > r || y < 1 || y > c)return 1000005;
    return c*(x-1)+y;
}
int main(){jizz
    cin >> r >> c;
    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= c; j++){
            bool o;cin >> o;
            box[h(i,j)] = o;
        }
    }
    for(int i = 1; i <= r; i++){
        for(int j = 1; j <= c; j++){
            if(j == 1)continue;
            a[h(i,j)] = a[h(i,j-1)];
            if(box[h(i,j)] && box[h(i,j-1)])a[h(i,j)]++;
        }
    }
    for(int j = 1; j <= c; j++){
        for(int i = 1; i <= r; i++){
            if(i == 1)continue;
            b[h(i,j)] = b[h(i-1,j)];
            if(box[h(i,j)] && box[h(i-1,j)])b[h(i,j)]++;
            a[h(i,j)] += a[h(i-1,j)];
        }
    }
    for(int i = 1; i <= r; i++)
        for(int j = 1; j <= c; j++)
            if(j != 1)b[h(i,j)] += b[h(i,j-1)];
    int q;cin >> q;
    while(q--){
        int r1,c1,r2,c2;cin >> r1 >> c1 >> r2 >> c2;
        int ans1 = a[h(r2,c2)]-a[h(r1-1,c2)]-a[h(r2,c1)]+a[h(r1-1,c1)];
        int ans2 = b[h(r2,c2)]-b[h(r1,c2)]-b[h(r2,c1-1)]+b[h(r1,c1-1)];
        cout << ans1 + ans2 << endl;
    }
    return 0;
}