C++ 代码
// 这道题的核心就是映射,因为不是每个位置都有值,所以我们想办法把位置缩小到可用范围内,然后得到对应的lr,再使用前缀和来求区间和
// 离散化,把无限空间中有限的个体映射到有限的空间中去,以此提高算法的时空效率。
// 通俗的说,离散化是在不改变数据相对大小的条件下,对数据进行相应的缩小。例如:
// 原数据:1,999,100000,15;处理后:1,3,4,2;
// 原数据:{100,200},{20,50000},{1,400};
// 处理后:{3,4},{2,6},{1,5};
// ————————————————
// 问题:
// a[]中存在重复的坐标:使用unique方法去重
// 找到a[i]映射之后的值:使用二分迅速找到对应位置
// 对应变量解释:
// vector<int> alls 所有的坐标
// -----------------------------------------------------------------------------------------------------------------
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 300010;//插入操作100000,里面一个坐标;查询操作100000,里面2个坐标,所以保险起见开个300010;
int n, m;
int a[N], s[N];
vector<int> alls;
vector<PII> add;
vector<PII> query;
int find(int x)
{
int l = 0, r = alls.size() - 1;
while(l < r)
{
int mid = l + r >> 1;
if (x <= alls[mid]) r = mid;
else l = mid + 1;
}
return l + 1;//因为要处理前缀和,习惯从1开始,不用额外处理边界
}
int main()
{
cin >> n >> m;
while (n -- )//进行n次插入操作,对 add 和 alls 进行插入
{
int x, c;
cin >> x >> c;
add.push_back({x, c});//add里面添加的是位置x和值c的pair
alls.push_back(x);//alls里面添加的是位置,x也是位置,通通加进去
}
while (m --)
{
int l, r;
cin >> l >> r;
query.push_back({l, r});//query数组里面存放需要求和的区间对
alls.push_back(l);//然后把这个区间对里面所有的坐标 l r 都提取出来,下一步就是对alls进行去重操作
alls.push_back(r);
}
//使用sort,erase,unique进行去重三件套
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
//处理插入:这里插入是插入到映射之后的数组中去了,新的value数组就是a[]
for(auto item : add)
{
int x = find(item.first);
a[x] += item.second; //这里题目说的是每次在当前位置添加c
}
// 预处理:前缀和数组-----a[] 和 s[] 在前面开了,就是前缀和数组与value数组
for(int i = 1; i <= alls.size(); i ++) s[i] = s[i - 1] + a[i];
// query映射结束之后,处理位置之间的区间和(代码就是那个前缀和)
for(auto item : query)
{
int l = find(item.first), r = find(item.second);//找到这两个数在映射之后的位置(pair中第一个元素叫first,第二个称为second)
cout << s[r] - s[l - 1] << endl;
}
return 0;
}
/*知识补充
1.去重:unique函数,配合sort函数和erase函数,可以得到一个数组的单个出现的值:
a.erase(unique(a.begin(), a.end()), a.end())
unique是将一个数组所有出现的第一次的值移到最前面,重复出现的放到后面,然后返回重复值的第一个下标
erase(first, last)删除从first到last
vector<int>::iterator unique(vector<int> &a)//这一段是unique的实现思路,cpp中可以直接用,java自己实现一下
{
int j = 0;
for(int i = 0; i < a.size(); i ++)
{
if (!i || a[i] != a[i - 1])
{
a[j] = a[i];
j ++;
}
return a.begin() + j;
}
}
2.键值对pair,习惯定义简写: typedef pair<int, int> PII; pair中第一个元素叫first,第二个称为second
*/
谢谢!完全懂了