AcWing 802. 区间和
原题链接
简单
作者:
Asteroid.W
,
2021-08-26 11:27:27
,
所有人可见
,
阅读 268
// 用一个新数组存放下标
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=300010; //坐标x的数量上限为1e5,两个坐标l,r的数量上限也为1e5,所以加起来为3*le5;
typedef pair<int,int> PII; //typedef定义了一个新的类型PII
int a[N],s[N]; // a数组存数,s数组存前缀和
vector<int> alls; // 将l,r,x的坐标值保存在alls中
vector<PII> add,query; // add存x和c, query存l和r
// 查找离散后的坐标
int find(int x)// 使用二分在alls数组中找值为x的下标(x是原数组的下标,映射前的下标)
{
int l=0,r=alls.size()-1;
while(l<r)
{
int mid=(l+r)/2;
if(alls[mid]>=x) r=mid; // 找到第一个大于等于x的值,在左边。
else l=mid+1;
}
return r+1;//因为后面要使用前缀和,所以下标要从1开始,要加1;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++)
{
int x,c;
cin>>x>>c;
add.push_back({x,c}); // 用来存n次操作
alls.push_back(x); // 将l,r,x的坐标值保存在alls中;
}
for(int i=0;i<m;i++)
{
int l,r;
cin>>l>>r;
query.push_back({l,r}); // 用来存m次询问
alls.push_back(l);
alls.push_back(r);
}
//到此为止,alls中存好了所有会被用到的数轴上的点
//将alls进行排序,alls存储的是所有操作即用到的下标,很明显,肯定会有重复的,为了方便离散化,我们去重,去重之后所存储的数目变少,降低了时间复杂度
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
// 处理插入
for(auto itdm : add) // itdm.first是x,是下标。second是c,是值。
{
int x;
x=find(itdm.first); // x是a数组的下标,是离散化后的下标加1。
a[x]+=itdm.second; // a数组存值
}
// 预处理前缀和
for(int i=1;i<=alls.size();i++) s[i]=s[i-1]+a[i];
// 处理询问
for(auto itdm : query)
{
int l,r;
l=find(itdm.first); //找出l,r在a中的坐标
r=find(itdm.second);
printf("%d\n",s[r]-s[l-1]); //前缀和上方已计算,所以可直接输出。
}
return 0;
}