如果询问 \(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;
}