ABC 366

Sat, Jan 25, 2025

D - Cuboid Sum Query

3次元累積和の問題

https://atcoder.jp/contests/abc366/tasks/abc366_d

$f_i(a,b) = \sum_{i=a}^{b}$ とする。

\begin{align} \sum_{i=a}^{x} &\sum_{i=b}^{y} \sum_{i=c}^{z} \nonumber = f_i(a,x)f_j(b,y)f_k(c,z) \nonumber \\ &= \left\{ f_i(1,x) - f_i(1,a-1) \right\} \nonumber \\ &~~~ \times \left\{ f_j(1,y) - f_j(1,b-1) \right\} \nonumber \\ &~~~ \times \left\{ f_k(1,z) - f_k(1,c-1) \right\} \nonumber \\ &= f_i(1,x)f_j(1,y)f_k(1,z) - f_i(1,x)f_j(1,y)f_k(1,c-1) \nonumber \\ &~~~ - f_i(1,x)f_j(1,b-1)f_k(1,z) + f_i(1,x)f_j(1,b-1)f_k(1,c-1) \nonumber \\ &~~~ - f_i(1,a-1)f_j(1,y)f_k(1,z) + f_i(1,a-1)f_j(1,y)f_k(1,c-1) \nonumber \\ &~~~ + f_i(1,a-1)f_j(1,b-1)f_k(1,z) - f_i(1,a-1)f_j(1,b-1)f_k(1,c-1) \nonumber \\ \end{align}

これより $\displaystyle S_{x,y,z} = \sum_{i=1}^{x} \sum_{j=1}^{y} \sum_{k=1}^{z} A_{i,j,k}$ とすると

\begin{align} \sum_{i=a}^{x} &\sum_{i=b}^{y} \sum_{i=c}^{z} A_{i,j,k} \nonumber \\ &= S_{x,y,z} - S_{x,y,c-1}- S_{x,b-1,z} + S_{x,b-1,c-1} \nonumber \\ &~~~ - S_{a-1,y,z} + S_{a-1,y,c-1} + S_{a-1,b-1,z} - S_{a-1,b-1,c-1} \nonumber \end{align}

3次元累積和がわかっているときに部分的な累積和を求める方法はわかった。

次に3次元累積和の構成方法について考える。

\begin{align} f_i(1,x)&f_j(1,y)f_k(1,z) \nonumber \\ &= \left\{ f_i(x,x) + f_i(1,x-1) \right\} \nonumber \\ &~~~ \times \left\{ f_j(y,y) + f_j(1,y-1) \right\} \nonumber \\ &~~~ \times \left\{ f_k(z,z) + f_k(1,z-1) \right\} \nonumber \\ &= f_i(x,x)f_j(y,y)f_k(z,z) + f_i(x,x)f_j(y,y)f_k(1,z-1) \nonumber \\ &~~~ + f_i(x,x)f_j(1,y-1)f_k(z,z) + f_i(x,x)f_j(1,y-1)f_k(1,z-1) \nonumber \\ &~~~ + f_i(1,x-1)f_j(y,y)f_k(z,z) + f_i(1,x-1)f_j(y,y)f_k(1,z-1) \nonumber \\ &~~~ + f_i(1,x-1)f_j(1,y-1)f_k(z,z) + f_i(1,x-1)f_j(1,y-1)f_k(1,z-1) \nonumber \end{align}

\begin{align} f_i(x,x)&f_j(y,y)f_k(1,z-1) \nonumber \\ &= \left\{ f_i(1,x) - f_i(1,x-1) \right\} \left\{ f_j(1,y) - f_j(1,y-1) \right\} f_k(1,z-1) \nonumber \\ &= f_i(1,x)f_j(1,y)f_k(1,z-1) - f_i(1,x)f_j(1,y-1)f_k(1,z-1) \nonumber \\ &~~~ - f_i(1,x-1)f_j(1,y)f_k(1,z-1) + f_i(1,x-1)f_j(1,y-1)f_k(1,z-1) \nonumber \end{align}

\begin{align} f_i(x,x)&f_j(1,y-1)f_k(z,z) \nonumber \\ &= \left\{ f_i(1,x) - f_i(1,x-1) \right\} f_j(1,y-1) \left\{ f_k(1,z) - f_k(1,z-1) \right\}\nonumber \\ &= f_i(1,x)f_j(1,y-1)f_k(1,z) - f_i(1,x)f_j(1,y-1)f_k(1,z-1) \nonumber \\ &~~~ - f_i(1,x-1)f_j(1,y-1)f_k(1,z) + f_i(1,x-1)f_j(1,y-1)f_k(1,z-1) \nonumber \end{align}

\begin{align} f_i(1,x-1)&f_j(y,y)f_k(z,z) \nonumber \\ &= f_i(1,x-1) \left\{ f_j(1,y) - f_j(1,y-1) \right\} \left\{ f_k(1,z) - f_k(1,z-1) \right\}\nonumber \\ &= f_i(1,x-1)f_j(1,y)f_k(1,z) - f_i(1,x-1)f_j(1,y)f_k(1,z-1) \nonumber \\ &~~~ - f_i(1,x-1)f_j(1,y-1)f_k(1,z) + f_i(1,x-1)f_j(1,y-1)f_k(1,z-1) \nonumber \end{align}

\begin{align} f_i(x,x)&f_j(1,y-1)f_k(1,z-1) \nonumber \\ &= \left\{ f_i(1,x) - f_i(1,x-1) \right\} f_j(1,y-1) f_k(1,z-1) \nonumber \\ &= f_i(1,x)f_j(1,y-1) f_k(1,z-1) - f_i(1,x-1)f_j(1,y-1)f_k(1,z-1) \nonumber \end{align}

\begin{align} f_i(1,x-1)&f_j(y,y)f_k(1,z-1) \nonumber \\ &= f_i(1,x-1) \left\{ f_j(1,y) - f_j(1,y-1) \right\} f_k(1,z-1) \nonumber \\ &= f_i(1,x-1)f_j(1,y)f_k(1,z-1) - f_i(1,x-1)f_j(1,y-1)f_k(1,z-1) \nonumber \end{align}

\begin{align} f_i(1,x-1)&f_j(1,y-1)f_k(z,z) \nonumber \\ &= f_i(1,x-1) f(1,y-1)\left\{ f_k(1,z) - f_k(1,z-1) \right\} \nonumber \\ &= f_i(1,x-1)f_j(1,y-1)f_k(1,z) - f_i(1,x-1)f_j(1,y-1)f_k(1,z-1) \nonumber \end{align}

まとめると

\begin{align} S_{x,y,z} &= A_{x,y,z} + S_{x,y,z-1} + S_{x,y-1,z} - S_{x,y-1,z-1} \nonumber \\ &+ S_{x-1,y,z} - S_{x-1,y,z-1} - S_{x-1,y-1,z} + S_{x-1,y-1,z-1} \nonumber \end{align}

累積和で終点を含む場合

void solve() {
    ll N;
    cin >> N;

    vector<vvll> A(N + 1, vvll(N + 1, vll(N + 1, 0)));
    rep(i, N) {
        rep(j, N) {
            rep(k, N) {
                cin >> A[i + 1][j + 1][k + 1];
            }
        }
    }

    vector<tuple<ll, ll, ll, ll>> d = {
        {0, 0, -1, 1},
        {0, -1, 0, 1},
        {0, -1, -1, -1},
        {-1, 0, 0, 1},
        {-1, 0, -1, -1},
        {-1, -1, 0, -1},
        {-1, -1, -1, 1},
    };

    vector<vvll> cumsum(N + 1, vvll(N + 1, vll(N + 1, 0)));
    rep2(i, 1, N + 1) rep2(j, 1, N + 1) rep2(k, 1, N + 1) {
        cumsum[i][j][k] += A[i][j][k];
        for (auto [x, y, z, sign] : d) {
            cumsum[i][j][k] += cumsum[i + x][j + y][k + z] * sign;
        }
    }

    ll Q;
    cin >> Q;
    while (Q--) {
        ll a, x, b, y, c, z;
        cin >> a >> x >> b >> y >> c >> z;

        ll ans = 0;
        ans += cumsum[x][y][z];
        ans -= cumsum[x][y][c - 1];
        ans -= cumsum[x][b - 1][z];
        ans += cumsum[x][b - 1][c - 1];
        ans -= cumsum[a - 1][y][z];
        ans += cumsum[a - 1][y][c - 1];
        ans += cumsum[a - 1][b - 1][z];
        ans -= cumsum[a - 1][b - 1][c - 1];
        cout << ans << endl;
    }
}

累積和で終点を含まない場合

void solve() {
    ll N;
    cin >> N;

    vector<vvll> A(N, vvll(N, vll(N, 0)));
    rep(i, N) {
        rep(j, N) {
            rep(k, N) {
                cin >> A[i][j][k];
            }
        }
    }

    vector<tuple<ll, ll, ll, ll>> d = {
        {0, 0, -1, 1},
        {0, -1, 0, 1},
        {0, -1, -1, -1},
        {-1, 0, 0, 1},
        {-1, 0, -1, -1},
        {-1, -1, 0, -1},
        {-1, -1, -1, 1},
    };

    vector<vvll> cumsum(N + 1, vvll(N + 1, vll(N + 1, 0)));
    rep2(i, 1, N + 1) rep2(j, 1, N + 1) rep2(k, 1, N + 1) {
        cumsum[i][j][k] += A[i - 1][j - 1][k - 1];
        for (auto [x, y, z, sign] : d) {
            cumsum[i][j][k] += cumsum[i + x][j + y][k + z] * sign;
        }
    }

    ll Q;
    cin >> Q;
    while (Q--) {
        ll a, x, b, y, c, z;
        cin >> a >> x >> b >> y >> c >> z;
        a--, b--, c--;

        ll ans = 0;
        ans += cumsum[x][y][z];
        ans -= cumsum[x][y][c];
        ans -= cumsum[x][b][z];
        ans += cumsum[x][b][c];
        ans -= cumsum[a][y][z];
        ans += cumsum[a][y][c];
        ans += cumsum[a][b][z];
        ans -= cumsum[a][b][c];
        cout << ans << endl;
    }
}

ABC 366

Table of Contents

D - Cuboid Sum Query