做法一：旋转坐标

令一个原坐标 $(r,c)$ 变成

对于一次以 $(x,y)$ 为中心、半径为 $d$ 的菱形操作，条件

等价于在新坐标中同时满足

也就是说，原来的菱形变成了新坐标系里的矩形。于是每次操作只需要在二维差分数组中对一个矩形加一，所有操作结束后做二维前缀和，再把每个原格子 $(r,c)$ 映射到 $(u,v)$ 取值即可。

注意：新坐标里不是每个点都对应原网格中的格子，但我们最后只查询原网格实际存在的点，所以不需要额外处理奇偶性。

复杂度：

• 时间复杂度：$O(m+n^2)$。
• 空间复杂度：$O(n^2)$。

参考代码：旋转坐标

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;


    const int lim = 2 * n + 2;
    vector<vector<int>> diff(lim + 3, vector<int>(lim + 3, 0));

    for (int i = 0; i < m; ++i) {
        int x, y, d;
        cin >> x >> y >> d;

        int u = x + y;
        int v = x - y + n;


        int u1 = max(1, u - d);
        int u2 = min(lim, u + d);
        int v1 = max(1, v - d);
        int v2 = min(lim, v + d);

        diff[u1][v1] += 1;
        diff[u2 + 1][v1] -= 1;
        diff[u1][v2 + 1] -= 1;
        diff[u2 + 1][v2 + 1] += 1;
    }


    for (int i = 1; i <= lim; ++i) {
        for (int j = 1; j <= lim; ++j) {
            diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1];
        }
    }


    for (int r = 1; r <= n; ++r) {
        for (int c = 1; c <= n; ++c) {
            int u = r + c;
            int v = r - c + n;
            if (c > 1) cout << ' ';
            cout << diff[u][v];
        }
        cout << '\n';
    }

    return 0;
}

做法二：不旋转坐标

仍然从“每个菱形在每一行上是一段区间”出发。

对于中心 $(x,y)$、半径 $d$ 的操作：

• 当 $r \le x$ 时，左端点是 $x+y-d-r$，右端点后一位是 $r+y+d-x+1$；
• 当 $r > x$ 时，左端点是 $r+y-d-x$，右端点后一位是 $x+y+d-r+1$。

也就是说，如果我们维护每一行的一维差分数组，那么每次操作会在若干行上产生两类点：

• 区间左端点处加 $1$；
• 区间右端点后一位处减 $1$。

这些端点随着行号变化时，恰好沿着斜率为 $1$ 或 $-1$ 的对角线移动。因此可以再做一次“对角线差分”：一次操作只需在几条对角线段上打标记，最后沿对角线前缀和还原出每一行的一维差分，再对每行做横向前缀和。

为了避免菱形超出网格边界时频繁截断列坐标，可以把列差分数组向左右多开一些。比如逻辑列坐标允许出现小于 $1$ 或大于 $n+1$ 的端点，横向前缀时从足够小的列开始扫，输出 $1$ 到 $n$ 列即可。

复杂度：

• 时间复杂度：$O(m+n^2)$。
• 空间复杂度：$O(n^2)$。

参考代码：不旋转坐标

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    const int off = 2 * n + 5;
    const int w = 5 * n + 20;

    vector<vector<int>> dr(n + 3, vector<int>(w + 3, 0));
    vector<vector<int>> dl(n + 3, vector<int>(w + 3, 0));

    auto add_dr = [&](int r1, int c1, int r2, int val) {
        if (r1 > r2) return;
        int c2 = c1 + (r2 - r1);
        dr[r1][c1 + off] += val;
        dr[r2 + 1][c2 + 1 + off] -= val;
    };

    auto add_dl = [&](int r1, int c1, int r2, int val) {
        if (r1 > r2) return;
        int c2 = c1 - (r2 - r1);
        dl[r1][c1 + off] += val;
        dl[r2 + 1][c2 - 1 + off] -= val;
    };

    for (int i = 0; i < m; ++i) {
        int x, y, d;
        cin >> x >> y >> d;

     
        int a = max(1, x - d);
        int b = min(n, x);
        if (a <= b) {
            add_dl(a, x + y - d - a, b, +1);
            add_dr(a, a + y + d - x + 1, b, -1);
        }


        a = max(1, x + 1);
        b = min(n, x + d);
        if (a <= b) {
            add_dr(a, a + y - d - x, b, +1);
            add_dl(a, x + y + d - a + 1, b, -1);
        }
    }


    for (int r = 1; r <= n; ++r) {
        for (int c = 1; c <= w; ++c) {
            dr[r][c] += dr[r - 1][c - 1];
        }
        for (int c = w; c >= 1; --c) {
            dl[r][c] += dl[r - 1][c + 1];
        }
    }


    for (int r = 1; r <= n; ++r) {
        int cur = 0;
        for (int logical_c = 1 - 2 * n; logical_c <= n; ++logical_c) {
            int idx = logical_c + off;
            cur += dr[r][idx] + dl[r][idx];

            if (1 <= logical_c && logical_c <= n) {
                if (logical_c > 1) cout << ' ';
                cout << cur;
            }
        }
        cout << '\n';
    }

    return 0;
}