二维差分进阶版----------三维差分
三维差分和二维差分类似,需要注意的就是(差分与前缀和的下标都从1开始,避免出现越界)
思路:从立方体的俯视图进行思考。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
typedef long long LL;
LL s[N][N][N], b[N][N][N];
void insert(int x1, int y1, int z1, int x2, int y2, int z2, int h)
{
/**
偶数个1是+
奇数个1是-
**/
b[x1][y1][z1] += h;
b[x1][y1][z2 + 1] -= h;
b[x1][y2 + 1][z1] -= h;
b[x1][y2 + 1][z2 + 1] += h;
b[x2 + 1][y1][z1] -= h;
b[x2 + 1][y1][z2 + 1] += h;
b[x2 + 1][y2 + 1][z1] += h;
b[x2 + 1][y2 + 1][z2 + 1] -= h;
}
int main()
{
LL q;
LL x, y, z;
LL x1, y1, z1, x2, y2, z2, h;
scanf("%lld%lld%lld", &x, &y, &z);
for (LL i = 1; i <= z; i ++ )
{
for (LL j = 1; j <= y; j ++ )
{
for (LL k = 1; k <= x; k ++ )
scanf("%lld", &s[i][j][k]);
}
}
for (LL i = 1; i <= z; i ++ )
{
for (LL j = 1; j <= y; j ++ )
{
for (LL k = 1; k <= x; k ++ )
insert(i, j, k, i, j, k, s[i][j][k]);
}
}
scanf("%lld", &q);
while (q -- )
{
scanf("%lld%lld%lld%lld%lld%lld%lld", &x1, &y1, &z1, &x2, &y2, &z2, &h);
insert(z1, y1, x1, z2, y2, x2, h);
}
for (LL i = 1; i <= z; i ++ )
{
for (LL j = 1; j <= y; j ++ )
{
for (LL k = 1; k <= x; k ++ )
{
b[i][j][k] +=
b[i - 1][j][k] + b[i][j - 1][k] - b[i - 1][j - 1][k] + b[i][j][k - 1] - b[i - 1][j][k - 1] - b[i][j - 1][k - 1] + b[i - 1][j - 1][k - 1];
}
}
}
for (LL i = 1; i <= z; i ++ )
{
for (LL j = 1; j <= y; j ++ )
{
for (LL k = 1; k <= x; k ++ )
cout << b[i][j][k] << " ";
cout << endl;
}
}
return 0;
}
常用规律
偶数个1是+
奇数个1是-
0 0 0 ------> +
0 0 1 ------> -
0 1 0 ------> -
0 1 1 ------> +
1 0 0 ------> -
1 0 1 ------> +
1 1 0 ------> +
1 1 1 ------> -