#include<iostream>
#include<vector>
#include<algorithm>
// #include<bits/stdc++.h>
using namespace std;
const int N = 300010;//插入十万个可以是不同的下标,查询20万个可以是不同的下标,总计a和s数组要保存30万
typedef pair<int,int> PII;
int n,m;
int a[N],s[N];
vector<int> alls;//存所有要离散化之后的值
vector<PII> add,query;
int find(int x){
// int l = 0,r = alls.size() - 1;
// while(l < r){
// int mid = l + r >> 1;
// if(alls[mid] >= x) r = mid;
// else l = mid + 1;
// }
// return r + 1;//下标从1开始 1 2 3... 前缀和好处理
return lower_bound(alls.begin(),alls.end(),x) - alls.begin() + 1;
}
int main(){
cin >> n >> m;
for(int i = 0;i < n;i ++){
int x,c;
cin >> x >> c;
add.push_back({x,c});
alls.push_back(x);
}
for(int i = 0;i < m;i ++){
int l,r;
cin >> l >> r;
query.push_back({l,r});
alls.push_back(l);
alls.push_back(r);
}
//alls 排序去重
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
for(auto item : add){
int x = find(item.first);
a[x] += item.second;
}
for(int i = 1;i <= alls.size();i ++){
s[i] = s[i - 1] + a[i];
}
for(auto q : query){
cout << s[find(q.second)] - s[find(q.first) - 1] << endl;
}
return 0;
}
重写unique函数
#include<iostream>
#include<vector>
#include<algorithm>
// #include<bits/stdc++.h>
using namespace std;
const int N = 300010;//插入十万个可以是不同的下标,查询20万个可以是不同的下标,总计a和s数组要保存30万
typedef pair<int,int> PII;
int n,m;
int a[N],s[N];
vector<int> alls;//存所有要离散化之后的值
vector<PII> add,query;
int find(int x){
// int l = 0,r = alls.size() - 1;
// while(l < r){
// int mid = l + r >> 1;
// if(alls[mid] >= x) r = mid;
// else l = mid + 1;
// }
// return r + 1;//下标从1开始 1 2 3... 前缀和好处理
return lower_bound(alls.begin(),alls.end(),x) - alls.begin() + 1;
}
vector<int>::iterator unique(vector<int> &a){//双指针
int j = 0;
for(int i = 0;i < a.size();i ++)
if(!i || a[i] != a[i - 1])
a[j ++] = a[i];
// 从 a[0] 到 a[j - 1] 就是所有a中所有具有唯一性的数了
return a.begin() + j;
}
int main(){
cin >> n >> m;
for(int i = 0;i < n;i ++){
int x,c;
cin >> x >> c;
add.push_back({x,c});
alls.push_back(x);
}
for(int i = 0;i < m;i ++){
int l,r;
cin >> l >> r;
query.push_back({l,r});
alls.push_back(l);
alls.push_back(r);
}
//alls 排序去重 因为题目询问的就是即使离散也是保序的区间 所以排序是必须的
sort(alls.begin(),alls.end());
alls.erase(unique(alls),alls.end());
for(auto item : add){
int x = find(item.first);
a[x] += item.second;
}
for(int i = 1;i <= alls.size();i ++){
s[i] = s[i - 1] + a[i];
}
for(auto q : query){
cout << s[find(q.second)] - s[find(q.first) - 1] << endl;
}
return 0;
}
偷mrk的板子
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 100005;
int d[N], tot = 0, a[N], c[N], sum[N];
int n, m;
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d%d", a + i, c + i);
d[++tot] = a[i];
}
sort(d + 1, d + 1 + tot);
tot = unique(d + 1, d + 1 + tot) - (d + 1);
for (int i = 1; i <= n; i++) {
int v = lower_bound(d + 1, d + 1 + tot, a[i]) - d;
sum[v] += c[i];
}
for (int i = 1; i <= tot; i++)
sum[i] += sum[i - 1];
while(m--) {
int l, r; scanf("%d%d", &l, &r);
l = lower_bound(d + 1, d + 1 + tot, l) - d;
r = upper_bound(d + 1, d + 1 + tot, r) - d - 1;
printf("%d\n", sum[r] - sum[l - 1]);
}
return 0;
}