AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 应用
  • 更多
    • 题解
    • 分享
    • 商店
    • 问答
    • 吐槽
  • App
  • 登录/注册

三维差分

作者: 作者的头像   浩然正气 ,  2023-03-19 17:51:36 ,  所有人可见 ,  阅读 57


1


二维差分进阶版----------三维差分

2023.png
三维差分和二维差分类似,需要注意的就是(差分与前缀和的下标都从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      ------>    -

希望各位大佬给予修正 谢谢

0 评论

你确定删除吗?
1024
x

© 2018-2023 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息