巨大チェスボード [技術室奥プログラミングコンテスト #3 D]

https://beta.atcoder.jp/contests/tkppc3/tasks/tkppc3_d

前提知識

• 累積和

考察過程

1. 各クエリでどのように愚直に計算するかを考えてみる
2. 例で挙げられているチェスボート全体で考えてみると、黒は(14+50)*(7+5) + 9*35のようにかける
3. 黒い部分の計算と白い部分の計算はそれぞれ累積和でなんとか行けそう
4. 奇数番目だけ、偶数番目だけの累積和に分けておけば計算ができるのでは？

解法

https://beta.atcoder.jp/contests/tkppc3/submissions/2840984

累積和を使って、各クエリを高速に処理していこう。
奇数番目のマスと偶数番目のマスでうまく分けて計算する。
　
AS[parity][i] := parity=j%2かつj≦iであるjについてA[j]の和を取ったもの
BS[parity][i] := parity=j%2かつj≦iであるjについてB[j]の和を取ったもの
これを用意しておこう。
関数getをget(l,r,v) := v[l] + v[l+1] + ... + v[r]として作っておく。
　
すると、各クエリについて、
黒い部分の面積はget(px, qx, AS[0]) * get(py, qy, BS[0]) + get(px, qx, AS[1]) * get(py, qy, BS[1])
白い部分の面積はget(px, qx, AS[0]) * get(py, qy, BS[1]) + get(px, qx, AS[1]) * get(py, qy, BS[0])
となるので、後は引き算して答えるだけ。

int H, W, Q;
ll A[101010], B[101010];
//---------------------------------------------------------------------------------------------------
ll get(int l, int r, vector<ll> &v) { // [l,r]
    ll res = v[r];
    if (l) res -= v[l - 1];
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W >> Q;
    rep(i, 0, H) cin >> A[i];
    rep(i, 0, W) cin >> B[i];
 
    vector<ll> AS[2];
    AS[0].resize(H, 0);
    AS[1].resize(H, 0);
    rep(i, 0, H) AS[i % 2][i] = A[i];
    rep(i, 0, 2) rep(j, 1, H) AS[i][j] += AS[i][j - 1];
 
    vector<ll> BS[2];
    BS[0].resize(W, 0);
    BS[1].resize(W, 0);
    rep(i, 0, W) BS[i % 2][i] = B[i];
    rep(i, 0, 2) rep(j, 1, W) BS[i][j] += BS[i][j - 1];
 
    rep(_, 0, Q) {
        int px, py, qx, qy;
        cin >> px >> py >> qx >> qy;
        px--; py--; qx--; qy--;
 
        ll a = get(px, qx, AS[0]) * get(py, qy, BS[0]) + get(px, qx, AS[1]) * get(py, qy, BS[1]);
        ll b = get(px, qx, AS[0]) * get(py, qy, BS[1]) + get(px, qx, AS[1]) * get(py, qy, BS[0]);
 
        ll ans = a - b;
        printf("%lld\n", ans);
    }
}