AcWing 802. 区间和
原题链接
简单
#include<iostream>
#include<vector>//c++用vector做离散化
#include<algorithm>
using namespace std;
typedef pair<int,int> PII; //用pair存每个要离散的数
const int N=300010; //插入操作总数是10万,查询操作总数是10w,插入操作有1个坐标,查询操作有2个坐标
int n,m;
int a[N],s[N];
vector<int> alls; //存的所有要离散化的值
vector<PII> add,query;
//求x离散化之后的结果
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; // 如果中间的值大于等于x,向左半部分搜索
else l=mid+1;// 否则向右半部分搜索
}
return r+1; // 返回x在离散化后数组中的位置,+1是为了映射从1开始的自然数
}
/*
使用二分查找法在 alls 中寻找 x 的位置。二分查找的核心是通过不断缩小搜索区间来找到目标值的下标:
计算中点 mid,并比较 alls[mid] 和 x。
如果 alls[mid] 大于或等于 x,说明 x 的位置不在 mid 右侧,因此将 r 移动到 mid,缩小搜索范围。
如果 alls[mid] 小于 x,则说明 x 在 mid 右侧,因此将 l 移动到 mid + 1,同样缩小搜索范围。
*/
int main()
{
cin>>n>>m; //先把所有要操作的数读进来,把里面用到的下标全部离散化
for(int i=0;i<n;i++)
{
int x,c; //在下标x的点加上c
cin>>x>>c;
add.push_back({x,c}); // 存储插入操作的坐标和数值
alls.push_back(x); //将x加入到要离散化的值集合中 //要把x离散化,则要把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);
}
//alls数组去重
sort(alls.begin(),alls.end());// 首先排序
alls.erase(unique(alls.begin(),alls.end()),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;
}