对alls(即下表)去重的原因?
》 alls存储的是所有操作即用到的下标,很明显,肯定会有重复的,为了方便离散化,我们去重,去重之后所存储的数目变少,降低了时间复杂度
为什么用到add, query?
>> add用于存放对原数组的操作, query用于存放求和的区间值,存储起来,为下面操作做准备
为什么用pair<int, int>?
>> 因为我们每次输入的是成对的
//核心:
去重: sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
//查找离散后的位置(下表从1开始)
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;
}
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5 * 3 + 5;
typedef pair<int, int> PII;
int m, n;
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;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
int x, c;
scanf("%d%d", &x, &c);
add.push_back({x, c});
alls.push_back(x);
}
for (int i = 0; i < m; i++) {
int l, r;
scanf("%d%d", &l, &r);
query.push_back({l, r});
alls.push_back(l);
alls.push_back(r);
}
//排序,去重
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
//处理add, 求a[]
for (auto it : add) {
int x = find(it.first);
a[x] += it.second;
}
//求前缀和
for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];
//处理询问
for (auto it : query) {
int l = find(it.first);
int r = find(it.second);
printf("%d\n", s[r] - s[l - 1]);
}
return 0;
}
谢谢谢谢,自己把过程写了一遍,终于理解了,看视频看得一头雾水
写的挺好的,给你点个赞吧!!!
Orz