[ABC366D] Cuboid Sum Query Problem Solving

[ABC366D] Cuboid Sum Query Problem Solving

Original Question Portal

AT Original Question Portal

Translation of the meaning of the title:

give\(N \times N \times N\) The three-dimensional matrix with\(Q\) times, and for each query, four numbers are given, namely\(L_1,R_1,L_2,R_2,L_3,R_3\) Seek in three-dimensional matrices\(a[L_1][L_2][L_3]\) until (a time)\(a[R_1][R_2][R_3]\) The intervals and.

Three-dimensional prefixes and board questions, although Ben Konjac is also presently learned, but this does not affect the questions. Walking.

The first is the initialization of the three-dimensional prefix sum, and we can handle the prefix sum one dimension at a time, with a triple loop:

int a[maxn][maxn][maxn]; // prefix and array
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        for(int k=1;k<=n;k++)
            a[i][j][k]+=a[i-1][j][k];
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        for(int k=1;k<=n;k++)
            a[i][j][k]+=a[i][j-1][k];
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        for(int k=1;k<=n;k++)
            a[i][j][k]+=a[i][j][k-1];

With the prefix sums taken care of, the question becomes how to find the interval sum.

Using the principle of capacitive repulsion, one can introduce an equation like this:

This is the answer that needs to be exported.

This question ends.

AC code：

#include <bits/stdc++.h>
#define seq(q, w, e) for (int q = w; q <= e; q++)
#define ll long long
using namespace std;
const int maxn = 110;
int n,t;
int a[maxn][maxn][maxn];
signed main()
{
    ios::sync_with_stdio(0);
    (0);(0);
    cin>>n;
    seq(i,1,n){
        seq(j,1,n){
            seq(k,1,n){
                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++) 
                a[i][j][k] += a[i - 1][j][k];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            for(int k = 1; k <= n; k++)
                a[i][j][k] += a[i][j - 1][k];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            for(int k = 1; k <= n; k++)
                a[i][j][k] += a[i][j][k - 1];
    cin>>t;
    while(t--){
        int b1,b2,b3,e1,e2,e3;
        cin>>b1>>e1>>b2>>e2>>b3>>e3;
        cout<<a[e1][e2][e3]-a[b1-1][e2][e3]-a[e1][b2-1][e3]-a[e1][e2][b3-1]+a[b1-1][b2-1][e3]+
        	  a[b1-1][e2][b3-1]+a[e1][b2-1][b3-1]-a[b1-1][b2-1][b3-1]<<endl;
    }
    return 0;
}