AcWing 802. 区间和
原题链接
简单
作者:
今天wzry凉了吗
,
2021-03-16 18:13:16
,
所有人可见
,
阅读 214
#include <iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;//用于运算和查询
const int N=300010;//2n+m+10
int a[N],s[N];//离散后的数组
vector<int>alls;//动态长度,记录数字
vector<PII>query,add;//动态长度,记录数字
int find(int x){
int l=0,r=alls.size()-1;
while(l<r){
int mid=(l+r)/2;
if(alls[mid]>=x) r=mid;
else l=mid+1; //注意这个加号
}
return l+1;//前缀和从1开始
}
int main()
{
int n,m,x,c,l,r;
cin>>n>>m;
for(int i=0;i<n;i++){
scanf("%d%d",&x,&c);
add.push_back({x,c});
alls.push_back(x);//只用加入位置即可,c是一样的
}
for(int i=0;i<m;i++){
scanf("%d%d",&l,&r);
query.push_back({l,r});
alls.push_back(l);
alls.push_back(r);//保证能用二分找到l,r;
}
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
for(auto item:add) a[find(item.first)]+=item.second;
//a中已经有元素之后,用前缀和啦
for(int i=1;i<=alls.size();i++) s[i]=s[i-1]+a[i];//前缀和从1开始
for(auto item:query){
int i=find(item.first);//find是在alls立面找的
int j=find(item.second);
printf("%d\n",s[j]-s[i-1]);
}
return 0;
}
代码前后加上三个点,就是这个```
好的谢谢大佬!