AcWing 802. 区间和
原题链接
简单
作者:
德智体美劳
,
2024-10-28 11:55:32
,
所有人可见
,
阅读 1
//小白结合大佬的理解写的,如有错误谢谢大佬指正
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 300010;
typedef pair<int,int> PII;
int a[N],s[N];
//用来存储待处理的下标
vector<int> alls;
//用来存储n个输入的数组
vector<PII> add; //存储了要插入的位置和插入的值
//用来存储m个输入的数组
vector<PII> query; //存储了要访问的左边界和右边界
//通过二分实现离散化
//这个find的函数实现的功能是利用二分来实现下标的重新映射,
//首先我们知道alls中存储的是排序去重后无规律的数组下标
//数组的长度为−10^9~10^9,所以alls中存储的数可能会很大
//而我们离散化的目的就是把这些数进行映射到一个更小的区间上
//通过find的中二分操作,我们可以关注到在find中的范围就是l=0,r=alls.size()-1 这就是我们映射的范围
//所以最后返回的值也只可能是这个范围0-alls.size()-1,即完成映射
int find(int x)
{
int l = 0;
int r = alls.size() - 1;
while(l < r)
{
int mid = (l + r) >> 1;
if(alls[mid] >= x) r = mid;
else l = mid + 1;
}
return l + 1;
}
int main()
{
int n,m;
cin>>n>>m;
//处理n行输入
for(int i = 0; i < n; i++)
{
int x,c;
cin>>x>>c;
add.push_back({x,c});
alls.push_back(x);
}
//处理m行输入
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中
//对alls进行去重和排序(才能进行二分查找,实现离散化)
sort(alls.begin(), alls.end());
alls.erase(unique(alls.begin(), alls.end()), alls.end());
//排序去重完毕,进行离散化操作
for(PII item:add)
{
int x = find(item.first);
a[x] += item.second;
}
//此时,需要插入的数值已经插入a中,a不再是一个全0的数组了
//对a进行求前缀和
for(int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];
//此时 要改变的值已经实现离散化
//接着对要访问的区间进行离散化从处理
for(PII item:query)
{
int l = find(item.first);
int r = find(item.second);
//要访问的区间已离散化
//要访问的数也已插入,插入的位置也已离散化
//所以此时直接前缀和求 l 到 r 之间的和即可
cout<<s[r] - s[l - 1]<<endl;
}
return 0;
}