solution.md

# 三体攻击


**题目描述**

三体人将对地球发起攻击。为了抵御攻击，地球人派出了 A × B × C 艘战舰，在太空中排成一个 A 层 B 行 C 列的立方体。其中，第 i 层第 j 行第 k 列的战舰（记为战舰 (i, j, k)）的生命值为 d(i, j, k)。

三体人将会对地球发起 m 轮“立方体攻击”，每次攻击会对一个小立方体中的所有战舰都造成相同的伤害。具体地，第 t 轮攻击用 7 个参数 $la_t, ra_t, lb_t, rb_t, lc_t, rc_t, h_t $描述；

所有满足$ i ∈ [la_t, ra_t],j ∈ [lb_t, rb_t],k ∈ [lc_t, rc_t] $的战舰 (i, j, k) 会受到 $h_t$ 的伤害。如果一个战舰累计受到的总伤害超过其防御力，那么这个战舰会爆炸。

地球指挥官希望你能告诉他，第一艘爆炸的战舰是在哪一轮攻击后爆炸的。


**输入格式**

从标准输入读入数据。

第一行包括 4 个正整数 A, B, C, m；  

第二行包含 A × B × C 个整数，其中第 ((i − 1)×B + (j − 1)) × C + (k − 1)+1 个数为 d(i, j, k)；  

第 3 到第 m + 2 行中，第 (t − 2) 行包含 7 个正整数 $la_t, ra_t, lb_t, rb_t, lc_t, rc_t, h_t$。


**输出格式**

输出到标准输出。

输出第一个爆炸的战舰是在哪一轮攻击后爆炸的。保证一定存在这样的战舰。


**样例输入**

```
2 2 2 3
1 1 1 1 1 1 1 1
1 2 1 2 1 1 1
1 1 1 2 1 2 1
1 1 1 1 1 1 2
```

**样例输出**

```
2
```

**样例解释**

在第 2 轮攻击后，战舰 (1,1,1) 总共受到了 2 点伤害，超出其防御力导致爆炸。


**数据约定**

```
对于 10% 的数据，B = C = 1；
对于 20% 的数据，C = 1；
对于 40% 的数据，A × B × C, m ≤ 10, 000；
对于 70% 的数据，A, B, C ≤ 200；
对于所有数据，A × B × C ≤ 10^6, m ≤ 10^6, 0 ≤ d(i, j, k), ht ≤ 10^9。
```

以下程序实现了这一功能，请你补全空白处的内容：

```c
#include <bits/stdc++.h>
using namespace std;

const int N = 2000010;

typedef long long LL;
int A, B, C, m;
LL s[N], b[N], bp[N];
int op[N / 2][7];

const int d[8][4] = {
    {0, 0, 0, 1},
    {0, 0, 1, -1},
    {0, 1, 0, -1},
    {0, 1, 1, 1},
    {1, 0, 0, -1},
    {1, 0, 1, 1},
    {1, 1, 0, 1},
    {1, 1, 1, -1}};

int get(int i, int j, int k)
{

    return (i * B + j) * C + k;
}

bool check(int mid)
{
    memcpy(b, bp, sizeof bp);
    for (int i = 1; i <= mid; i++)
    {
        int x1 = op[i][0], x2 = op[i][1], y1 = op[i][2], y2 = op[i][3], z1 = op[i][4], z2 = op[i][5], h = op[i][6];
        b[get(x1, y1, z1)] -= h;
        b[get(x1, y1, z2 + 1)] += h;
        b[get(x1, y2 + 1, z1)] += h;
        b[get(x1, y2 + 1, z2 + 1)] -= h;
        b[get(x2 + 1, y1, z1)] += h;
        b[get(x2 + 1, y1, z2 + 1)] -= h;
        b[get(x2 + 1, y2 + 1, z1)] -= h;
        b[get(x2 + 1, y2 + 1, z2 + 1)] += h;
    }

    memset(s, 0, sizeof s);
    for (int i = 1; i <= A; i++)
        for (int j = 1; j <= B; j++)
            for (int k = 1; k <= C; k++)
            {
                s[get(i, j, k)] = b[get(i, j, k)];
                for (int u = 1; u < 8; u++)
                {
                    int x = i - d[u][0], y = j - d[u][1], z = k - d[u][2], t = d[u][3];
                    s[get(i, j, k)] -= s[get(x, y, z)] * t;
                }

                if (s[get(i, j, k)] < 0)
                    return true;
            }

    return false;
}

int main()
{
    scanf("%d%d%d%d", &A, &B, &C, &m);

    for (int i = 1; i <= A; i++)
        for (int j = 1; j <= B; j++)
            for (int k = 1; k <= C; k++)
                scanf("%lld", &s[get(i, j, k)]);

    for (int i = 1; i <= A; i++)
        for (int j = 1; j <= B; j++)
            for (int k = 1; k <= C; k++)
                for (int u = 0; u < 8; u++)
                {
                    int x = i - d[u][0], y = j - d[u][1], z = k - d[u][2], t = d[u][3];
                    __________________
                }

    for (int i = 1; i <= m; i++)
        for (int j = 0; j < 7; j++)
            scanf("%d", &op[i][j]);

    int l = 1, r = m;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }

    printf("%d\n", r);
    return 0;
}
```

## 答案

```c
bp[get(i, j, k)] += s[get(x, y, z)] * t;
```

## 选项

### A

```c
bp[get(i, j, k)] = s[get(x, y, z)] * t;
```

### B

```c
bp[get(i, j, k)] *= s[get(x, y, z)] * t;
```

### C

```c
bp[get(i, j, k)] = s[get(x, y, z)] + t;
```