如果询问 $x_1, y_1, x_2, y_2$，

那么询问

$(x_2, y_2)$,

$(x_2, y_1 - 1)$,

$(x_1 - 1, y_2)$

$(x_1 - 1, y_1 - 1$),

这些点到原点（不一定是 $(0, 0)$，有可能有负数）的和。

设其结果分别为 $a, b, c, d$，那么最后结果为 $a - b - c + d$（二维前缀和原理）。

问题成功转化。

设结构体

struct Node {
	int x, y;		// 位置
	int z;			// 值
};

为基本信息。

我们在此基础上加一个 $type$ 和 $res$，

如果 $type$ 为 $1$ 就表示要询问 $(x, y)$ 的二维前缀和，结果保存在 $res$ 中。

如果 $type$ 为 $0$ 表示 $(x, y)$ 为一个基站，其功率为 $z$。

对于 $type_i$ 为 $1$ 的部分，

使用 CDQ 分治统计：

$type_j < type_i$ (即 $type_j$ 为 $0$)

$x_j \leq x_i$

$y_j \leq y_i$

的各个位置的和即可。

注意开long long。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map> 

#define int long long 

using namespace std;

const int N = 500010;

struct Node {
	int x, y, z;
	int type;
	int res;
}a[N], tmp[N];

bool cmp(const Node a, const Node b) {
	if (a.x != b.x) return a.x < b.x;
	if (a.y != b.y) return a.y < b.y;
	return a.type < b.type;
}

int n, m;

void cdq(int l, int r) {
	if (l == r) return;
	int mid = (l + r) / 2;
	cdq(l, mid);
	cdq(mid + 1, r);
	
	int sum = 0;
	
	int p = l, q = mid + 1, tot = l;
	while (p <= mid && q <= r) {
		if (a[p].y <= a[q].y) {
			if (!a[p].type) sum += a[p].z;
			tmp[tot++] = a[p++];
		}
		else {
			if (a[q].type) a[q].res += sum;
			tmp[tot++] = a[q++];
		}
	}
	while (p <= mid) {
		if (!a[p].type) sum += a[p].z;
		tmp[tot++] = a[p++];
	}
	while (q <= r) {
		if (a[q].type) a[q].res += sum;
		tmp[tot++] = a[q++];
	}
	for (int i = l; i <= r; i++) a[i] = tmp[i];
}

struct Query {
	int x1, y1;
	int x2, y2;
}query[N];

unordered_map<int, unordered_map<int, int> > res_a;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].x >> a[i].y >> a[i].z;
		a[i].type = 0;
		a[i].res = 0;
	}
	int tot = n;
	for (int i = 1; i <= m; i++) {
		cin >> query[i].x1 >> query[i].y1 >> query[i].x2 >> query[i].y2;
		a[++tot] = {query[i].x1 - 1, query[i].y1 - 1, 0, 1, 0};
		a[++tot] = {query[i].x2, query[i].y2, 0, 1, 0};
		a[++tot] = {query[i].x2, query[i].y1 - 1, 0, 1, 0};
		a[++tot] = {query[i].x1 - 1, query[i].y2, 0, 1, 0};
	}
	sort(a + 1, a + tot + 1, cmp);
	cdq(1, tot);
	for (int i = 1; i <= tot; i++) {
		if (a[i].type) {
			res_a[a[i].x][a[i].y] = a[i].res;
		}
	}
	for (int i = 1; i <= m; i++) {
		int x1 = query[i].x1, y1 = query[i].y1;
		int x2 = query[i].x2, y2 = query[i].y2;
		
		int ans = res_a[x2][y2] - res_a[x2][y1 - 1] - res_a[x1 - 1][y2] + res_a[x1 - 1][y1 - 1];
		cout << ans << '\n';
	}
	return 0;
}