AcWing 802. 区间和(关键代码数据解释)
原题链接
简单
作者:
xirang_hu
,
2024-04-11 16:21:48
,
所有人可见
,
阅读 5
区间和
标签: 离散化+二分+前缀和
C++ 代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N = 300010; //离散化后的操作数为n+2m
typedef pair<int,int> PII; //存储操作数对,这里是一对数
int a[N],s[N]; // a[N] 存储原序列,s[N]存储前缀和
vector <int> alls; //存储待离散化的数值(这里是指数轴上的位置x)
vector<PII> add,query; //add表示插入操作数,query插入待求的区间
int n,m;
int find(int x) // 4. 二分求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; // 注意这里是r+1,这样可以是离散化后的结果从1开始,方便前缀和
}
int main()
{
cin>>n>>m;
/* 1. 完成初始化操作:
将用到的操作数插入给定的序列中,
将需要离散化的数插入到专门的vector
*/
for(int i=0;i<n;i++)
{
int x,c;
cin>>x>>c;
add.push_back({x,c});// 将数对添加到addl里
alls.push_back(x); // 由于需要将x离散化,所以将x添加到待离散化的vector
}
//2. 接下来读入左右区间,因为左右区间是原始序列中的,所有都需要离散化
for(int i=0;i<m;i++)
{
int l,r;
cin>>l>>r;
query.push_back({l,r});
// 将l和r都加入到待里里离散化的vector数组中
// 注意这里也添加到alls中进行离散化,因为后面会根据这个来输出区间和
// 可能会和前面的x有重合,对应到了后面的去重操作
alls.push_back(l);
alls.push_back(r);
}
// 3. 去重
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
// 5.执行题目的加数操作
for(auto it : add)
{
int x = find(it.first);
a[x] += it.second;
}
// 6. 预处理前缀和
int t = alls.size();
for(int i=1;i<=t;i++)
{
s[i] = s[i-1] + a[i];
}
// 7. 处理每次询问,也就是输出结果
for(auto it : query)
{
int l = find(it.first),r = find(it.second);
cout<<s[r]-s[l-1]<<endl;
}
return 0;
}