题目链接：HDU 4456

F 市的地图是一个 $n\times n$ 的网格，对于每个交叉口，我们为其定义一个人群密集度。最初，每个交叉口的密集度为 $0$；随着时间的推移，密集度可能会变化。为了计算密集度，警察局的管理人员提出了“$k$ 维密集度”的概念。交叉口 $(x_0,y_0)$ 的“$k$ 维密集度”用 $c(x_0,y_0,k)$ 表示，可以用下式计算：

$$ c(x_0,y_0,k)=\sum_{\vert x-x_0\vert +\vert y-y_0\vert \le k} d(x,y) $$

其中 $d(x,y)$ 为交叉口 $(x,y)$ 的密集度。

此时一共有 $m$ 个操作，操作问题如下 $2$ 个类型：

• 1 x y z：路口 $(x,y)$ 的密集度 $d(x,y)$ 增加了 $z$。
• 2 x y z：询问 $c(x,y,z)$ 的值。

数据范围：$1\le n\le 10^4$，$1\le m\le 8\times 10^4$，对于操作 $1$ 有 $-100\le z\le 100$，对于操作 $2$ 有 $0\le z\le 2n-1$。

Solution

首先我们把整个网格旋转 $45^\circ$，那么点 $(x,y)$ 变成点 $(x-y,x+y)$，也就是说把曼哈顿距离变成了切比雪夫距离，我们要求的从一个菱形变成了一个矩形。于是可以把矩形拆成 $4$ 个前缀和统计了。

考虑 $\text{CDQ}$ 分治，我们对时间分治，合并时第一关键字为行 $x$，第二关键字为询问类型（修改优先），第三关键字为列 $y$，按照套路做就行了。

时间复杂度：$\mathcal O(m\log n)$。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 4e4 + 5, M = 4e5 + 5;

int n, m, ans[M];

struct Data {
    int p, x, y, k, q, idx;
    Data() {}
    Data(int _p, int _x, int _y, int _k, int _q, int _idx) {
        p = _p, x = _x, y = _y, k = _k, q = _q, idx = _idx;
    }
} a[M], t[M];

struct BIT {
    int Max, b[N];
    void init() {
        Max = 4 * n;
        memset(b, 0, sizeof(b));
    }
    void modify(int x, int v) {
        for (; x <= Max; x += x & -x) b[x] += v;
    }
    int query(int x) {
        int ans = 0;
        for (; x; x ^= x & -x) ans += b[x];
        return ans;
    }
} bit;

bool cmp(Data a, Data b) {
    return a.x == b.x ? a.p == b.p ? a.y < b.y : a.p < b.p : a.x < b.x;
}
void CDQ(int l, int r) {
    if (l == r) return;
    int m = (l + r) >> 1;
    CDQ(l, m), CDQ(m + 1, r);
    std::merge(a + l, a + m + 1, a + m + 1, a + r + 1, t + l, cmp);
    std::copy(t + l, t + r + 1, a + l);
    for (int i = l; i <= r; i++) {
        if (a[i].idx <= m) {
            if (a[i].p == 1) bit.modify(a[i].y, a[i].k);
        } else {
            if (a[i].p == 2) ans[a[i].q] += a[i].k * bit.query(a[i].y);
        }
    }
    for (int i = l; i <= r; i++) {
        if (a[i].idx <= m && a[i].p == 1) bit.modify(a[i].y, -a[i].k);
    }
}
int main() {
    while(~scanf("%d", &n) && n) {
        scanf("%d", &m);
        int T = 0, tot = 0;
        for (int i = 1; i <= m; i++) {
            int p, x, y, k;
            scanf("%d%d%d%d", &p, &x, &y, &k);
            if (p == 1) {
                tot++, a[tot] = Data(p, x - y + n, x + y, k, 0, tot);
            } else {
                T++;
                int X = x - y + n, Y = x + y;
                int x1 = std::max(X - k - 1, 1), y1 = std::max(Y - k - 1, 1), x2 = X + k, y2 = Y + k;
                tot++, a[tot] = Data(p, x1, y1, 1, T, tot);
                tot++, a[tot] = Data(p, x2, y1, -1, T, tot);
                tot++, a[tot] = Data(p, x1, y2, -1, T, tot);
                tot++, a[tot] = Data(p, x2, y2, 1, T, tot);
            }
        }
        bit.init();
        memset(ans, 0, sizeof(ans));
        CDQ(1, tot);
        for (int i = 1; i <= T; i++) printf("%d\n", ans[i]);
    }
    return 0;
}