对于每一次询问，三角形的三个顶点分别为 $A(x+d, y), B(x, y), C(x, y+d)$。一个点 $(X, Y)$ 在该三角形内部或边界上，必须同时满足以下三个条件：

1. $X \ge x$；
2. $Y \ge y$；
3. $X + Y \le x + y + d$；

令 $S = x + y + d$。我们要求的是满足 $N(X \ge x \land Y \ge y \land X+Y \le S)$ 的点的数量。

直接统计较为困难，我们采用容斥原理，考虑其对立事件 $X < x$（即 $X \le x-1$）和 $Y < y$（即 $Y \le y-1$）：

$\text{Ans} = N(X+Y \le S) - N(X < x \land X+Y \le S) - N(Y < y \land X+Y \le S) + N(X < x \land Y < y \land X+Y \le S)$

观察第四项 $N(X < x \land Y < y \land X+Y \le S)$：

如果 $X \le x-1$ 且 $Y \le y-1$，那么必然有 $X+Y \le x+y-2$。由于题目中 $d \ge 0$，因此 $S = x+y+d \ge x+y > x+y-2$。

这意味着只要前两个条件成立，第三个条件 $X+Y \le S$ 必然成立。

因此，第四项可以直接化简为标准的二维矩形查询 $N(X < x \land Y < y)$。

最终答案分解为四项简单查询：

• $N(X+Y \le S)$ —— 全局一维前缀和。
• $N(X \le x-1 \land X+Y \le S)$ —— 按照 $X$ 坐标扫描线，维护 $X+Y$ 的树状数组。
• $N(Y \le y-1 \land X+Y \le S)$ —— 按照 $Y$ 坐标扫描线，维护 $X+Y$ 的树状数组。
• $N(X \le x-1 \land Y \le y-1)$ —— 可以在计算第二项的扫描线中，同步维护一个关于 $Y$ 的树状数组来求得。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

#define N 1000005
#define S 3000005

struct P {
    int x, y, z;
} p[N];

struct Q {
    int x, y, s, id;
} q[N];

struct BIT {
    int n;
    vector<int> c;
    BIT(int n) : n(n), c(n + 1, 0) {}
    void change(int x, int v) {
        for (; x <= n; x += x & -x) c[x] += v;
    }
    int get(int x) {
        int res = 0;
        for (; x > 0; x -= x & -x) res += c[x];
        return res;
    }
    void clear() {
        fill(c.begin(), c.end(), 0);
    }
} A(S), B(N);

int n, m;
int pre[S];
int ans[N];

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &p[i].x, &p[i].y);
        p[i].z = p[i].x + p[i].y;
        pre[p[i].z]++;
    }
    // 第一项: 预处理 Z = X + Y 的全局前缀和
    for (int i = 1; i < S; i++) {
        pre[i] += pre[i - 1];
    }
    for (int i = 1, d; i <= m; i++) {
        scanf("%d %d %d", &q[i].x, &q[i].y, &d);
        q[i].s = q[i].x + q[i].y + d;
        q[i].id = i;
        ans[i] += pre[q[i].s]; // 答案加上第一项
    }
    // 扫描线 1: 求解第二项和第四项
    // 按照 X 坐标升序排序
    sort(p + 1, p + n + 1, [](const P &a, const P &b) { return a.x < b.x; });
    sort(q + 1, q + m + 1, [](const Q &a, const Q &b) { return a.x < b.x; });
    for (int x = 0, i = 1, j = 1; x < N; x++) {
        while (i <= n && p[i].x == x) {
            A.change(p[i].z, 1);
            B.change(p[i].y, 1);
            i++;
        }
        while (j <= m && q[j].x - 1 == x) {
            ans[q[j].id] -= A.get(q[j].s);     // 减去第二项
            ans[q[j].id] += B.get(q[j].y - 1); // 加上第四项
            j++;
        }
    }
    // 扫描线 2: 求解第三项
    // 按照 Y 坐标升序排序
    sort(p + 1, p + n + 1, [](const P &a, const P &b) { return a.y < b.y; });
    sort(q + 1, q + m + 1, [](const Q &a, const Q &b) { return a.y < b.y; });
    A.clear();
    for (int y = 0, i = 1, j = 1; y < N; y++) {
        while (i <= n && p[i].y == y) {
            A.change(p[i].z, 1);
            i++;
        }
        while (j <= m && q[j].y - 1 == y) {
            int id = q[j].id;
            ans[id] -= A.get(q[j].s); // 减去第三项
            j++;
        }
    }
    for (int i = 1; i <= m; i++) printf("%d\n", ans[i]);
    return 0;
}

三维偏序模板. 虽然过不去。

1. 定义：假的三偏序，为可以用二偏序来做的三偏序。

2. 通过熔池，转化之。

3. 得出结论，扫描线即可。