三维（差分+前缀和）应用_三维前缀和

Description：三体攻击

三体人将对地球发起攻击。
为了抵御攻击，地球人派出了 A × B × C 艘战舰，在太空中排成一个 A 层 B 行 C 列的立方体。其中，第i 层第 j 行第 k 列的战舰（记为战舰 (i, j, k)）的生命值为 d(i, j, k)。三体人将会对地球发起 m 轮“立方体攻击”，每次攻击会对一个小立方体中的所有战舰都造成相同的伤害。
具体地，第 t 轮攻击用 7 个参数lat, rat, lbt, rbt, lct, rct, ht 描述；所有满足
i ∈ [lat, rat],j ∈ [lbt, rbt],k ∈ [lct, rct] 的战舰 (i, j, k) 会受到 ht的伤害。
如果一个战舰累计受到的总伤害超过其防御力，那么这个战舰会爆炸。
地球指挥官希望你能告诉他，第一艘爆炸的战舰是在哪一轮攻击后爆炸的。

思路1：暴力求解

暴力求解的方法是依次进行每一轮攻击，然后更新攻击范围内的战舰的生命值，当第t轮某一个战舰的血量小于0，那么直接返回 t.

思路2：二分+差分+前缀和

利用二分，第一次连续攻击m/2轮，然后判断战舰的生命值，如果此时没有战舰爆炸，那么再往后攻击m/4轮；如果此时有战舰爆炸，那么往前恢复m/4轮。不断二分，直到找到是在第几轮攻击时导致战舰爆炸。
那么怎么实现连续攻击m/2轮？
利用差分数组，再求前缀和

一、前缀和的概念：

例如，给出一组数 arr[ 1 , 2 , 3 , 4 , 5 ]
其前缀和 Sn[ 1, 3 , 6 , 10 , 15 ]
即 Sn[i] = Sn[i-1] + arr[i];

二、前缀和的特点：

1. O(N)的时间维护
   例如，arr[2] += 3;
   则Sn[ 1, 3 , 6+3 , 10+3 , 15+3 ]
2. O(1)的时间获取区间和
   例如，求在 [2,4] 的区间内数值和
   即 Sn[4] - Sn[1] = 15 - 3 = 12

三、一维差分数组+前缀和：

四、二维差分数组+前缀和：

五、三维差分数组+前缀和：

1、三维差分数组

给定三个角的坐标la , ra , lb , rb , lc , rc和攻击力h
正面四个
arr[lc][lb][la] += h;
arr[rc+1][lb][la] -= h;
arr[lc][lb][ra+1] -= h;
arr[rc+1][lb][ra+1] += h;
左面补两个
arr[lc][rb+1][la] -= h;
arr[lc][rb+1][ra+1] += h;
上面再补两个
arr[rc+1][rb+1][la] += h;
arr[rc+1][rb+1][ra+1] -= h;
2、三维前缀和

画的很乱，建议各位自己试着画一画。
arr[i][j][k] += arr[i][j-1][k]; //后方
arr[i][j][k] += arr[i-1][j][k];//左侧
arr[i][j][k] += arr[i][j][k-1]; //下方
arr[i][j][k] -= arr[i-1][j-1][k]; //左后
arr[i][j][k] -= arr[i-1][j][k-1]; //左下
arr[i][j][k] -= arr[i][j-1][k-1]; //后下
arr[i][j][k] += arr[i-1][j-1][k-1]; //左后下

六、算法实现

1. 暴力求解

    private static int[] arr;
    private static int[][] attacks;
    private static int A,B,C,m;
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        A = cin.nextInt();
        B = cin.nextInt();
        C = cin.nextInt();
        m = cin.nextInt();
        arr = new int[(A+1)*(B+1)*(C+1)];
        attacks = new int[m+1][7];
        //初始化战舰生命值
        for (int i = 1;i < A+1;i++){
            for (int j = 1;j < B+1;j++){
                for (int k = 1;k < C+1;k++){
                    arr[getIndex(i,j,k)] = cin.nextInt();
                }
            }
        }

        //执行攻击
        for (int k = 1; k < m+1; k++) {
            for (int m = 0;m < 7;m++) //读入攻击信息。
                attacks[k][m] = cin.nextInt();

            for (int i = attacks[k][0];i <= attacks[k][1];i++){
                for (int j = attacks[k][2]; j <= attacks[k][3]; j++) {
                    for (int l = attacks[k][4]; l <= attacks[k][5]; l++) {
                        arr[getIndex(i,j,l)] -= attacks[k][6];
                        if (arr[getIndex(i,j,l)] < 0) {
                            System.out.println();
                            System.out.println(k);
                            return;
                        }
                    }
                }
            }
        }

    }

    static int getIndex(int i, int j, int k){
        return (((i-1)*(B+1)+(j-1))*(C+1)+k);
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

2. 二分+差分+前缀和

private static int A, B, C, a, b, c, m;
    private static int[][] attack;//攻击
    private static int[] diff;//差分数组

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        A = cin.nextInt();
        B = cin.nextInt();
        C = cin.nextInt();
        m = cin.nextInt();
        a = A + 1;
        b = B + 1;
        c = C + 1;
        attack = new int[m + 1][7];//m次攻击
        diff = new int[a * b * c];//差分数组(也是战舰生命值数组）

        cin.nextLine();//吃掉换行符
        //战舰生命值初始化(相当于给战舰回血）
        for (int i = 1; i < a; i++) {
            for (int j = 1; j < b; j++) {
                for (int k = 1; k < c; k++) {
                    op(i, i, j, j, k, k, cin.nextInt());
                }
            }
        }

        cin.nextLine();
        //输入每轮攻击范围和强度
        for (int i = 1; i <= m; i++) {
            for (int j = 0; j < 7; j++) {
                attack[i][j] = cin.nextInt();
            }
            cin.nextLine();
        }

        //二分攻击
        int l = 1, r = m, mid, lastMid = 0;
        while (l < r) {
            mid = (l + r) >> 1;
            if (mid > lastMid) {//说明战舰还没爆炸,需要继续进攻
                for (int i = lastMid + 1; i <= mid; i++)
                    op(attack[i][0], attack[i][1], attack[i][2], attack[i][3], attack[i][4], attack[i][5], -attack[i][6]);
            }
            if (mid < lastMid) {//说明已经有战舰爆炸，需要撤销进攻
                for (int i = mid + 1; i <= lastMid; i++)
                    op(attack[i][0], attack[i][1], attack[i][2], attack[i][3], attack[i][4], attack[i][5], attack[i][6]);
            }
            if (check())
                r = mid;
            else
                l = mid + 1;
            lastMid = mid;
        }

        System.out.println(r);
    }

    static boolean check() {//求前缀和
        int[] temp = new int[a * b * c];
        System.arraycopy(diff, 0, temp, 0, a * b * c);
        for (int i = 1; i < a; i++) {
            for (int j = 1; j < b; j++) {
                for (int k = 1; k < c; k++) {
                    if (j - 1 > 1)
                        diff[getIndex(i, j, k)] += diff[getIndex(i, j - 1, k)];
                    if (k - 1 > 1)
                        diff[getIndex(i, j, k)] += diff[getIndex(i, j, k - 1)];
                    if (i - 1 > 1)
                        diff[getIndex(i, j, k)] += diff[getIndex(i - 1, j, k)];
                    if (i - 1 > 1 && j - 1 > 1)
                        diff[getIndex(i, j, k)] -= diff[getIndex(i - 1, j - 1, k)];
                    if (i - 1 > 1 && k - 1 > 1)
                        diff[getIndex(i, j, k)] -= diff[getIndex(i - 1, j, k - 1)];
                    if (j - 1 > 1 && k - 1 > 1)
                        diff[getIndex(i, j, k)] -= diff[getIndex(i, j - 1, k - 1)];
                    if (i - 1 > 1 && j - 1 > 1 && k - 1 > 1)
                        diff[getIndex(i, j, k)] += diff[getIndex(i - 1, j - 1, k - 1)];

                    if (diff[getIndex(i, j, k)] < 0)//如果当前战舰爆炸了
                        return true;
                }
            }
        }
        return false;//所有战舰都没爆炸
    }

    static int getIndex(int i, int j, int k) {
        return (((i - 1) * (B + 1) + (j - 1)) * (C + 1) + k);
    }

    static void op(int la, int ra, int lb, int rb, int lc, int rc, int m) {
        //正面
        diff[getIndex(la, lb, lc)] += m;
        if (rb + 1 < b)
            diff[getIndex(la, rb + 1, lc)] -= m;
        if (ra + 1 < a)
            diff[getIndex(ra + 1, lb, lc)] -= m;
        if (ra + 1 < a && rb + 1 < b)
            diff[getIndex(ra + 1, rb + 1, lc)] += m;
        //左面
        if (rc + 1 < c)
            diff[getIndex(la, lb, rc + 1)] -= m;
        if (ra + 1 < a && rc + 1 < c)
            diff[getIndex(ra + 1, lb, rc + 1)] += m;
        //上面
        if (ra + 1 < a && rb + 1 < b && rc + 1 < c)
            diff[getIndex(ra + 1, rb + 1, rc + 1)] -= m;
        if (rb + 1 < b && rc + 1 < c)
            diff[getIndex(la, rb + 1, rc + 1)] += m;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110