##### $B = 1$ 时：
从前往后扫，维护滑动窗口即可。
```cpp
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 维护。
```cpp
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]$ 了。
```cpp
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);
}
}
```