自动搬运

查看原文

来自洛谷，原作者为

	圣嘉然 **

搬运于2025-08-24 22:02:16，当前版本为作者最后更新于2021-10-11 15:18:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

一个目前没人写在题解区的做法。

$B = 1$ 和 $B = 2$ 的部分就不展开说了，这里放一下一句话题解和代码。

$B = 1$ 时：

从前往后扫，维护滑动窗口即可。

namespace sub1 {
    const int N = 1e5 + 5;
    int p[N];

    inline void main(int n, int d, int m) {
        for (int i = 1; i <= n; ++i) 
            p[i] = read();
        std::sort(p + 1, p + n + 1);
        i64 res = 0;
        for (int i = 1, j = 1; i <= n; ++i) {
            while (j < i && p[i] - p[j] > d) ++j;
            res += i - j;
        }
        write(res);
    }
}

$B = 2$ 时：

二维曼哈顿距离转切比雪夫距离，按照 $x$ 排序后维护 $x$ 的滑动窗口，接下来变成 $y$ 这一维的区间求和，可以用 bit 维护。

namespace sub2 {
    const int N = 1e5 + 5, M = 75010;
    struct Node {
        int x, y;
    } p[N];

    int c[M * 2];
    inline void upd(int x, int v) {
        for (; x < M * 2; x += x & -x) 
            c[x] += v;
    }
    inline int qry(int x) {
        x = std::min(x, M * 2 - 1);
        int res = 0;
        for (; x > 0; x -= x & -x) 
            res += c[x];
        return res;
    }

    inline void main(int n, int d, int m) {
        for (int i = 1; i <= n; ++i) {
            int x = read(), y = read();
            p[i].x = x + y, p[i].y = x - y; // m -> q 
        }
        std::sort(p + 1, p + n + 1, [&](Node a, Node b) { return a.x < b.x; });
        i64 res = 0;
        for (int i = 1, j = 1; i <= n; ++i) {
            while (j < i && p[i].x - p[j].x > d) upd(p[j].y + m, -1), ++j;
            res += qry(p[i].y + d + m) - qry(p[i].y - d - 1 + m);
            upd(p[i].y + m, 1);
        }
        write(res);
    }
}

$B = 3$ 时：

因为有了 $B = 2$ 的做法，自然是想着能不能把三维曼哈顿距离转切比雪夫距离。

尝试推广，三维曼哈顿距离如下：

$$|x1−x2|+|y1−y2|+|z1−z2|$$

考虑暴力拆出 8 个 max，也就是暴力讨论每个绝对值的正负，这时候你发现三个绝对值全负和全正是一样的，不过是加了一个负号，而切比雪夫的距离公式中包含绝对值，所以可以把两项合并，于是最终两两合并，我们可以得到这个式子就等于：

$$ \max \{ |(x_1 + y_1 + z_1) - (x_2 + y_2 + z_2)|, |(x_1 + y_1 - z_1) - (x_2 + y_2 - z_2)|, |(x_1 - y_1 + z_1) - (x_2 - y_2 + z_2)|, |(x_1 - y_1 - z_1) - (x_2 - y_2 - z_2)| \} $$

于是如果将 $(x, y, z)$ 映射到 $(x + y + z, x + y - z, x - y + z, x - y - z)$，那么新的切比雪夫距离就是原来的曼哈顿距离。

按照第一维排序，剩下的问题就是查询一个三维立方体内部点的个数，树套树套树，考虑三维树状数组维护三维前缀和，查询的时候大力三维差分求立方体内部点个数。

为了让值域更小，可以把最后一维改成 $-x + y + z$，这样我们的值域就是 $[-m, 2m]$ 了。

namespace sub3 {
    const int N = 1e5 + 5, M = 83;
    struct Node {
        int a, b, c, d;
    } p[N];
    int c[M * 3][M * 3][M * 3]; // 三维 bit 
    inline void upd(int x, int y, int z, int v) {
        for (int i = x; i < M * 3; i += i & -i) {
            for (int j = y; j < M * 3; j += j & -j) {
                for (int k = z; k < M * 3; k += k & -k) {
                    c[i][j][k] += v;
                }
            }
        }
    }
    inline int qry(int x, int y, int z) {
        x = std::min(x, M * 3 - 1), y = std::min(y, M * 3 - 1), z = std::min(z, M * 3 - 1);
        int res = 0;
        for (int i = x; i > 0; i -= i & -i) {
            for (int j = y; j > 0; j -= j & -j) {
                for (int k = z; k > 0; k -= k & -k) {
                    res += c[i][j][k];
                }
            }
        }
        return res;
    }
    inline int ask(int lx, int rx, int ly, int ry, int lz, int rz) {
        int res = qry(rx, ry, rz); // 全集 需要减去 左面, 下面, 前面 的并集, 使用容斥
        res -= qry(lx, ry, rz) + qry(rx, ly, rz) + qry(rx, ry, lz);
        res += qry(lx, ly, rz) + qry(lx, ry, lz) + qry(rx, ly, lz);
        res -= qry(lx, ly, lz);
        // bug: 容斥这里写错两次 ... 传进来的就是 -1, 此处不需要 -1, -= 里面应该用 + 连接而非 - 
        return res;
    }

    inline void main(int n, int d, int m) {
        for (int i = 1; i <= n; ++i) {
            int x = read(), y = read(), z = read();
            p[i].a = x + y + z, p[i].b = x + y - z, p[i].c = x - y + z, p[i].d = -x + y + z;
        }
        std::sort(p + 1, p + n + 1, [&](Node a, Node b) { return a.a < b.a; });
        i64 res = 0;
        for (int i = 1, j = 1; i <= n; ++i) {
            while (j < i && p[i].a - p[j].a > d) {
                upd(p[j].b + m, p[j].c + m, p[j].d + m, -1), ++j;
            }
            res += ask(p[i].b - d - 1 + m, p[i].b + d + m, p[i].c - d - 1 + m, p[i].c + d + m, p[i].d - d - 1 + m, p[i].d + d + m);

            upd(p[i].b + m, p[i].c + m, p[i].d + m, 1);
        }
        write(res);
    }
}