C++ pair的基本用法总结(整理)_sevenjoin的博客-CSDN博客_c++ pair
for(auto i : v)遍历容器元素 - ostartech - 博客园 (cnblogs.com)
#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef pair<int, int> PII; const int N = 300010; 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开始,便于后续求前缀和 } 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); } // 去重 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 item : query) { int l = find(item.first), r = find(item.second); cout << s[r] - s[l - 1] << endl; } return 0; } 作者:yxc 链接:https://www.acwing.com/activity/content/code/content/40105/ 来源:AcWing 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。