AT_abc366_d [ABC366D] Cuboid Sum Query 题解

Snowflake_Fairy · 2024-08-12 13:47:03 · 题解

解题思路

首先看了看数据范围，发现 1 \le Q \le 2 \times 10^5，暴力算法的时间复杂度为 \mathcal{O}(n^3q)，很明显是会超时的，但这道题目明显可以预处理，然后就想到了前缀和。

只不过是三维前缀和而已，公式的推导方法与二维前缀和类似，主要思想是容斥，这里不再赘述，如果需要请参考这篇文章。

CODE：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 110;
int a[N][N][N];
int sum[N][N][N];
signed main() {
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    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) {
                sum[i][j][k] = a[i][j][k]
                + (i > 1 ? sum[i - 1][j][k] : 0)
                + (j > 1 ? sum[i][j - 1][k] : 0)
                + (k > 1 ? sum[i][j][k - 1] : 0)
                - (i > 1 && j > 1 ? sum[i - 1][j - 1][k] : 0)
                - (i > 1 && k > 1 ? sum[i - 1][j][k - 1] : 0)
                - (j > 1 && k > 1 ? sum[i][j - 1][k - 1] : 0)
                + (i > 1 && j > 1 && k > 1 ? sum[i - 1][j - 1][k - 1] : 0);
            }
        }
    }
    int q;
    cin >> q;
    while (q--) {
        int lx, rx, ly, ry, lz, rz;
        cin >> lx >> rx >> ly >> ry >> lz >> rz;
        cout << sum[rx][ry][rz]
        - (lx > 1 ? sum[lx - 1][ry][rz] : 0)
        - (ly > 1 ? sum[rx][ly - 1][rz] : 0)
        - (lz > 1 ? sum[rx][ry][lz - 1] : 0)
        + (lx > 1 && ly > 1 ? sum[lx - 1][ly - 1][rz] : 0)
        + (lx > 1 && lz > 1 ? sum[lx - 1][ry][lz - 1] : 0)
        + (ly > 1 && lz > 1 ? sum[rx][ly - 1][lz - 1] : 0)
        - (lx > 1 && ly > 1 && lz > 1 ? sum[lx - 1][ly - 1][lz - 1] : 0) << endl;
    }
    return 0;
}