题目：P8666 [蓝桥杯 2018 省 A] 三体攻击 - 洛谷( 三维差分 + 二分 )

思路：将"第几次攻击后有点被摧毁"转化为"前 mid 次攻击后的伤害累积"，用三维差分高效计算。

三维差分计算方法：（记忆口诀：一正三负三正一负（与三维二项式展开的系数一致））


    for (int i = 1; i <= a; i++) {
        for (int j = 1; j <= b; j++) {
            for (int k = 1; k <= c; k++) {
                cin >> edges[i][j][k];
                ddd[i][j][k] += edges[i][j][k];
                ddd[i + 1][j][k + 1] += edges[i][j][k];
                ddd[i + 1][j + 1][k] += edges[i][j][k];
                ddd[i][j + 1][k + 1] += edges[i][j][k];
                ddd[i + 1][j][k] -= edges[i][j][k];
                ddd[i][j + 1][k] -= edges[i][j][k];
                ddd[i][j][k + 1] -= edges[i][j][k];
                ddd[i + 1][j + 1][k + 1] -= edges[i][j][k];
            }
        }
    }

三维前缀和计算方法：

    for (int i = 1; i <= a ; i++) {
        for (int j = 1; j <= b; j++) {
            for (int k = 1; k <= c; k++) {
                ddd[i][j][k] += ddd[i - 1][j][k] + ddd[i][j - 1][k] + ddd[i][j][k - 1]
                    - ddd[i - 1][j - 1][k] - ddd[i - 1][j][k - 1] - ddd[i][j - 1][k - 1]
                    + ddd[i - 1][j - 1][k - 1];
            }
        }
    }

AC代码：O((n + m) × log m)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'

struct Node {
    int la, ra, lb, rb, lc, rc;
    ll h;
    Node(int _la, int _ra, int _lb, int _rb, int _lc, int _rc, ll _h) :la(_la), ra(_ra), lb(_lb), rb(_rb), lc(_lc), rc(_rc), h(_h) {}
};

ll can(int x, vector<Node>& mv,vector<vector<vector<ll>>> ddd,int a,int b,int c) {
    for (int i = 0; i < x; i++) {
        ddd[mv[i].la][mv[i].lb][mv[i].lc] += mv[i].h;
        ddd[mv[i].la][mv[i].rb + 1][mv[i].rc + 1] += mv[i].h;
        ddd[mv[i].ra + 1][mv[i].lb][mv[i].rc + 1] += mv[i].h;
        ddd[mv[i].ra + 1][mv[i].rb + 1][mv[i].lc] += mv[i].h;
        ddd[mv[i].ra + 1][mv[i].rb + 1][mv[i].rc + 1] -= mv[i].h;
        ddd[mv[i].la][mv[i].lb][mv[i].rc + 1] -= mv[i].h;
        ddd[mv[i].la][mv[i].rb + 1][mv[i].lc] -= mv[i].h;
        ddd[mv[i].ra + 1][mv[i].lb][mv[i].lc] -= mv[i].h;
    }
    for (int i = 1; i <= a ; i++) {
        for (int j = 1; j <= b; j++) {
            for (int k = 1; k <= c; k++) {
                ddd[i][j][k] += ddd[i - 1][j][k] + ddd[i][j - 1][k] + ddd[i][j][k - 1]
                    - ddd[i - 1][j - 1][k] - ddd[i - 1][j][k - 1] - ddd[i][j - 1][k - 1]
                    + ddd[i - 1][j - 1][k - 1];
                if (ddd[i][j][k] < 0) {
                    return false;
                }
            }
        }
    }
    return true;
}

void solve() {
    int a, b, c, m;
    cin >> a >> b >> c >> m;
    vector<vector<vector<ll>>> edges(a + 2, vector<vector<ll>>(b + 2, vector<ll>(c + 2)));
    vector<vector<vector<ll>>> ddd(a + 2, vector<vector<ll>>(b + 2, vector<ll>(c + 2)));
    for (int i = 1; i <= a; i++) {
        for (int j = 1; j <= b; j++) {
            for (int k = 1; k <= c; k++) {
                cin >> edges[i][j][k];
                ddd[i][j][k] += edges[i][j][k];
                ddd[i + 1][j][k + 1] += edges[i][j][k];
                ddd[i + 1][j + 1][k] += edges[i][j][k];
                ddd[i][j + 1][k + 1] += edges[i][j][k];
                ddd[i + 1][j][k] -= edges[i][j][k];
                ddd[i][j + 1][k] -= edges[i][j][k];
                ddd[i][j][k + 1] -= edges[i][j][k];
                ddd[i + 1][j + 1][k + 1] -= edges[i][j][k];
            }
        }
    }
    vector<Node> mv;
    for (int i = 0; i < m; i++) {
        int la, ra, lb, rb, lc, rc;
        ll h;
        cin >> la >> ra >> lb >> rb >> lc >> rc >> h;
        mv.push_back(Node(la, ra, lb, rb, lc, rc, -h));
    }
    int l = 0, r = m;
    while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (can(mid, mv, ddd,a,b,c)) {
            l = mid;
        }
        else {
            r = mid - 1;
        }
    }
    cout << l + 1 << endl;
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int _ = 1;
    //cin >> _;
    while (_--) {
        solve();
    }
    return 0;
}