https://www.acwing.com/problem/content/804/
#include <iostream> #include <vector> #include <algorithm> #include<bits/stdc++.h> using namespace std; typedef pair<int, int> PII; const int N = 300010; int n, m; int a[N], s[N]; //a是数字 s是前缀和 vector<int> alls; //存离散化之前的坐标 存的所有要离散化的值 vector<PII> add, query;//add是插入,query是求 int find(int x) { //求一下x这个值离散化之后的结果 找到第一个大于等于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开始 方便求前缀和 } int main() { cin >> n >> m; for (int i = 0; i < n; i ++ ) { int x, c; cin >> x >> c; add.push_back({x, c}); //在下标位x 的位置加上c alls.push_back(x); //把待离散化的坐标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); } //此时已经把所有需要用到的下标放到了all数组里 // 去重 把all数组去重 //可能又重复的元素 sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(),alls.end()), alls.end()); //unique是将数组中重复的元素去重,并且返回去重之后数组的尾端点 ,再用erase删除到原来尾端点之间的数字 // 处理插入 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 item : query) { int l = find(item.first), r = find(item.second); cout << s[r] - s[l - 1] << endl; } return 0; }
#include <iostream> #include <vector> #include <algorithm> #include<bits/stdc++.h> using namespace std; typedef pair<int, int> PII; const int N = 300010; int n, m; int a[N], s[N]; //a是数字 s是前缀和 vector<int> alls; //存离散化之前的坐标 存的所有要离散化的值 vector<PII> add, query;//add是插入,query是求 int main() { cin >> n >> m; for (int i = 0; i < n; i ++ ) { int x, c; cin >> x >> c; add.push_back({x, c}); //在下标位x 的位置加上c alls.push_back(x); //把待离散化的坐标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); } //此时已经把所有需要用到的下标放到了all数组里 // 去重 把all数组去重 //可能又重复的元素 sort(alls.begin(), alls.end()); alls.erase(unique(alls.begin(),alls.end()), alls.end()); //unique是将数组中重复的元素去重,并且返回去重之后数组的尾端点 ,再用erase删除到原来尾端点之间的数字 // 处理插入 for (auto item : add) { auto x = lower_bound(alls.begin(),alls.end(),item.first)- alls.begin() +1; //先求离散化之后的结果 a[x] += item.second; //在离散化之后的坐标上加上要加的数 } // 预处理前缀和 for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i]; // 处理询问 for (auto item : query) { auto l = lower_bound(alls.begin(),alls.end(),item.first)- alls.begin() +1; auto r = lower_bound(alls.begin(),alls.end(),item.second)- alls.begin() +1; cout << s[r] - s[l - 1] << endl; } return 0; }