- C++
离散化思想
- 2025-3-19 21:12:54 @
//请根据老师要求完成练习
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
struct opt {
int x, c;
};
struct query {
int l, r;
};
opt opts[N];
query q[N];
int all[3 * N], allx[3 * N];
long long pre[3 * N], t[3 * N];
int n, m, k;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> opts[i].x >> opts[i].c;
all[++k] = opts[i].x;
}
for (int i = 1; i <= m; i++) {
cin >> q[i].l >> q[i].r;
all[++k] = q[i].l;
all[++k] = q[i].r;
}
sort(all + 1, all + k + 1);
int cnt = unique(all + 1, all + k + 1) - (all + 1);
for (int i = 1; i <= n; i++) {
int idx = lower_bound(all + 1, all + cnt + 1, opts[i].x) - all;
t[idx] += opts[i].c;
}
for (int i = 1; i <= cnt; i++) {
pre[i] = pre[i - 1] + t[i];
}
for (int i = 1; i <= m; i++) {
int l = lower_bound(all + 1, all + cnt + 1, q[i].l) - all;
int r = lower_bound(all + 1, all + cnt + 1, q[i].r) - all;
cout << pre[r] - pre[l - 1] << endl;
}
return 0;
}
0 条评论
目前还没有评论...