ABC366D Cuboid Sum Query

Tag：高维前缀和

题目描述

给定一个正整数 \(N\) 和满足 \(1 \leq x, y, z \leq N\) 的整数组 \((x, y, z)\)，对于每个组合都有一个整数 \(A_{x, y, z}\)。

现在给出 \(Q\) 个查询，每个查询要求如下：

对于第 \(i\) 个查询 \((1 \leq i \leq Q)\)，给出一组整数 \((Lx_i, Rx_i, Ly_i, Ry_i, Lz_i, Rz_i)\)，其中 \(1 \leq Lx_i \leq Rx_i \leq N,\ 1 \leq Ly_i \leq Ry_i \leq N, 1 \leq Lz_i \leq Rz_i \leq N\)。要求计算并输出以下求和结果：

\[ \sum_{x=Lx_i}^{Rx_i}\ \sum_{y=Ly_i}^{Ry_i}\ \sum_{z=Lz_i}^{Rz_i}\ A_{x,y,z} \]

数据说明：

\(1 \leq N \leq 100\)
\(1 \leq Q \leq 2 \times 10^{5}\)
\(0 \leq A_{x,y,z} \leq 999\) \((1 \leq x, y, z \leq N)\)
\(1 \leq Lx_i \leq Rx_i \leq N\) \((1 \leq i \leq Q)\)
\(1 \leq Ly_i \leq Ry_i \leq N\) \((1 \leq i \leq Q)\)
\(1 \leq Lz_i \leq Rz_i \leq N\) \((1 \leq i \leq Q)\)

分析

三维前缀和板子题，直接写就过了。

代码实现

int a[105][105][105],s[105][105][105];
void NeverSayNever() {
    int n;cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++)cin >> a[i][j][k];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++)
                s[i][j][k] =
                        s[i][j][k - 1] + s[i][j - 1][k] + s[i - 1][j][k] 
                        - s[i - 1][j - 1][k] - s[i - 1][j][k - 1] - s[i][j - 1][k - 1] 
                        + s[i - 1][j - 1][k - 1] 
                        + a[i][j][k];
        }
    }
    int q; cin >> q;
    while (q--) {
        int x,xx,y,yy,z,zz;
        cin >> x >> xx >> y >> yy >> z >> zz;
        cout << s[xx][yy][zz] 
                - s[xx][yy][z - 1] - s[xx][y - 1][zz] - s[x - 1][yy][zz] 
                + s[x - 1][y - 1][zz] + s[x - 1][yy][z - 1] + s[xx][y - 1][z - 1]
                - s[x - 1][y - 1][z - 1] << endl;
    }
}

日志

本页面创建于 2024/8/17 20:38