#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
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;
}
int main() {
/*
n为n次操作,x为操作的位置,c为操作的位置上加上c
m为m次询问,询问l与r之间的所有数和
*/
std::ios::sync_with_stdio(false);//取消同步放心用cin读入数据
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.begin(), alls.end()), alls.end());//去除重复的元素
/*
(1) erase(pos,n); 删除从pos开始的n个字符,例如erase(0,1),
删除0位置的一个字符,即删除第一个字符
(2) erase(position);
删除position处的一个字符(position是个string类型的迭代器)
(3) erase(first,last);删除从first到last之间的字符,
(first和last都是迭代器) last不能是x.end()
unique 使用必须要先过一遍sort排序,再者unique函数返回值是一个迭代器
,它指向的是去重后容器中不重复序列的最后一个元素的下一个元素,所以如果
想要得到不重复元素的股数就需要用返回值-开始地址
*/
for (auto item : add) {//先对添加里的元素映射 赋值
int x = find(item.first);//找到x的映射值 往原数组中加c
a[x] += item.second; //处理插入
}
/* for(auto a:b)中b为一个容器,效果是利用a遍历并获得b容器中的每一个值
* 但是a无法影响到b容器中的元素
*/
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;
}
//每个元素都对应一组{first,first}键值对(pair),
//键值对中的第一个成员称为first,第二个成员称为second.
return 0;
}
这段代码是一个用于解决一个问题的实现,该问题要求用户对一个数组执行一系列操作。每个操作都包括在数组中指定索引范围内的每个元素上加上指定值。代码还支持查询在数组中指定索引范围内所有元素的总和。
代码使用一个向量来存储操作和查询,然后使用 std::sort() 函数对向量进行排序。代码然后使用 std::unique() 函数从向量中删除重复的元素。代码还定义了一个 find() 函数,该函数使用二分查找来查找向量中给定元素的位置。
代码使用前缀和数组来存储到给定索引为止数组中元素的总和。每次对数组执行操作时更新前缀和数组。回答查询时,代码使用 find() 函数找到查询的左右边界在前缀和数组中的位置,然后返回前缀和数组中这些位置处元素的总和之差。
为了更好地理解这段代码,让我们一步一步地分析它的工作原理。
首先,代码从输入读取操作和查询的个数:
cin >> n >> m;
然后,代码读入每个操作,并将它们存储在一个 vector 中:
for (int i = 0; i < n; i++) {
int x, c;
cin >> x >> c;
add.push_back({ x,c });
alls.push_back(x);
}
对于每个查询,代码同样读入查询的左右边界,并将它们存储在一个 vector 中:
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 中重复的元素:
alls.erase(unique(alls.begin(), alls.end()), alls.end());
接下来,对于每个操作,代码使用 find() 函数找到操作的位置在 alls 中的下标,并将指定值加到该位置上:
for (auto p : add) {
int x = p.first, c = p.second;
int pos = find(x);
s[pos] += c;
}
最后,对于每个查询,代码找到查询的左右边界在 alls 中的下标,并返回该边界下标之间的和:
for (auto q : query) {
int l = q.first, r = q.second;
int posl = find(l), posr = find(r);
cout << s[posr] - s[posl - 1] << endl;
}