不习惯vector版本,贴个数组版本离散化吧
C++ 代码
#include <algorithm>
#include <iostream>
#include <cstdio>
#define fi first
#define se second
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 1e5 + 10;
PII a[N],b[N];
LL c[3 * N];
int tot[3 * N];
int n,m;
void insert(int l, int r,int val){
c[l] += val;
c[r + 1] -= val;
}
int main(){
scanf("%d%d", &n, &m);
int cnt = 0;
for(int i = 1;i <= n; ++ i){
int x, c;
scanf("%d%d", &x, &c);
a[i] = {x, c};
tot[++ cnt] = x;
}
for(int i = 1; i <= m; ++ i){
int l, r;
scanf("%d%d", &l, &r);
b[i] = {l, r};
tot[++ cnt] = l;
tot[++ cnt] = r;
}
sort(tot + 1,tot + 1 + cnt);
cnt = unique(tot + 1, tot + 1 + cnt) - tot - 1;
for(int i = 1; i <= n; ++ i){
a[i].fi = lower_bound(tot + 1, tot + 1 + cnt, a[i].fi) - tot;
int x = a[i].fi;
int y = a[i].se;
insert(x, x, y);
}
for(int i = 1; i <= cnt; ++ i) c[i] += c[i-1];
for(int i = 1; i <= cnt; ++ i) c[i] += c[i-1];
for(int i = 1; i <= m; ++ i){
int x = lower_bound(tot + 1, tot + 1 + cnt, b[i].fi) - tot;
int y = lower_bound(tot + 1, tot + 1 + cnt, b[i].se) - tot;
printf("%lld\n", c[y] - c[x - 1]);
}
return 0;
}