题目描述
老 C 是个程序员。
最近老 C 从老板那里接到了一个任务——给城市中的手机基站写个管理系统。作为经验丰富的程序员，老 C 轻松地完成了系统的大部分功能，并把其中一个功能交给你来实现。
由于一个基站的面积相对于整个城市面积来说非常的小，因此每个的基站都可以看作坐标系中的一个点，其位置可以用坐标 (x,y) 来表示。此外，每个基站还有很多属性，例如高度、功率等。运营商经常会划定一个区域，并查询区域中所有基站的信息。
现在你需要实现的功能就是，对于一个给定的矩形区域，回答该区域中（包括区域边界上的）所有基站的功率总和。如果区域中没有任何基站，则回答 0。
输入格式
第一行两个整数 n,m，表示一共有 n 个基站和 m 次查询。接下来一共有 n 行，每行由 xi,yi,pi 三个空格隔开的整数构成，表示一个基站的坐标 (xi,yi) 和功率 pi。不会有两个基站位于同一坐标。
接下来一共有 m 行，每行由 x1,y1,x2,y2 四个空格隔开的整数构成，表示一次查询的矩形区域。该矩形对角坐标为 (x1,y1) 和 (x2,y2)，且边与坐标轴平行。
输出格式
输出 m 行，每行一个整数，对应每次查询的结果。
输入输出样例
输入 #1
4 2 0 0 1 0 1 2 2 2 4 1 0 8 0 0 1 1 1 1 5 6
输出 #1
11 4
输入 #2
3 2 -100 0 16 1 -10 32 1000 100 64 0 0 0 1 -1000 -1000 10000 10000
输出 #2
0 112
可持久化线段树 (主席树) + 离散化
类似求矩形之和
第 i 个版本表示从版本0 到到版本i 中所有功率之和，（左右边界）
再根据 y1 , y2， 固定上界与下界 （上下边界）
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<tuple>
#define inf 72340172838076673
#define int long long
#define endl '\n'
#define F first
#define S second
#define mst(a,x) memset(a,x,sizeof (a))
using namespace std;
typedef pair<int, int> pii;
const int N = 200086, mod = 998244353;
int n, m;
vector<int> yy;
int root[N], idx;
struct node {
int x, y, val;
node(int x1 = 0, int y1 = 0, int val1 = 0): x(x1), y(y1), val(val1) {}
bool operator<(const node &b)const { return x < b.x; }
} e[N];
struct tree {
int l, r;//左子树 右子树
int s; //区间功耗之和
} tr[N * 20];
bool cmp(node a, node b) {
return a.x < b.x;
}
//build 可写可不写
// int build(int l, int r) {
// int p = ++idx;
// if (l == r) return p;
// int mid = l + r >> 1;
// tr[p].l = build(l, mid);
// tr[p].r = build(mid + 1, r);
// return p;
// }
int insert(int p, int l, int r, int y, int v) {
int q = ++idx;
tr[q] = tr[p];
tr[q].s += v;
if (l == r) return q;
int mid = l + r >> 1;
if (y <= mid) tr[q].l = insert(tr[p].l, l, mid, y, v);
else tr[q].r = insert(tr[p].r, mid + 1, r, y, v);
return q;
}
int query(int u, int l, int r, int low, int up) {
if (low > r || up < l) return 0;
if (low <= l && r <= up) return tr[u].s;
int mid = l + r >> 1;
return query(tr[u].l, l, mid, low, up) + query(tr[u].r, mid + 1, r, low, up);
}
void solve() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
int a, b, c;
cin >> a >> b >> c;
e[i] = {a, b, c};
yy.push_back(b);
}
//对y轴离散化
sort(yy.begin(), yy.end());
yy.erase(unique(yy.begin(), yy.end()), yy.end());
sort(e + 1, e + n + 1, cmp);//对x坐标排序
for (int i = 1; i <= n; i++) {
e[i].y = lower_bound(yy.begin(), yy.end(), e[i].y) - yy.begin() + 1;
}
// root[0] = build(1, yy.size());
//更新版本
for (int i = 1; i <= n; i++) {
root[i] = insert(root[i - 1], 1, yy.size(), e[i].y, e[i].val);
}
for (int i = 1; i <= m; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int l = lower_bound(e + 1, e + n + 1, node(x1, 0)) - e;
int r = upper_bound(e + 1, e + n + 1, node(x2, 0)) - e - 1;//最后一个符合范围的位置
int low = lower_bound(yy.begin(), yy.end(), y1) - yy.begin() + 1;
int up = upper_bound(yy.begin(), yy.end(), y2) - yy.begin();
cout << query(root[r], 1, yy.size(), low, up) - query(root[l - 1], 1, yy.size(), low, up) << endl;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr), cout.tie(nullptr);
int T = 1;
// cin >> T;
while (T--) solve();
return 0;
}