AcWing 802. 区间和(超级详解版)
原题链接
简单
作者:
E.lena
,
2020-07-21 22:24:31
,
所有人可见
,
阅读 6786
#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;
vector<PII> add,query;
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 r+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});
alls.push_back(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);
}
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
for(auto itdm : add)
{
int x;
x=find(itdm.first);
a[x]+=itdm.second;
}
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);
r=find(itdm.second);
printf("%d\n",s[r]-s[l-1]);
}
return 0;
}
//一个迭代器从1开始直到末尾结束,itdm.first是x,second是r(在上方循环中可知);
这句注释中,second应该是c吧
说得对
虽然前面的题解图文并茂但是我就是转不过来为啥要去重,看完这篇终于懂了,,感谢
vector<int> alls; vector<int> a; vector<int> sum; vector<pair<int, int>> add, requir;
我想问一下,问什么前面vector[HTML_REMOVED] alls;
vector[HTML_REMOVED] a;
vector[HTML_REMOVED] sum;
vector[HTML_REMOVED]> add, requir;
这么写不行啊??是因为太占内存空间了么
终于懂了,谢谢
赞
tql
//一个迭代器从1开始直到末尾结束,itdm.first是x,second是r(在上方循环中可知);
second是c吧?
我也觉得是,应该是他打错了
tql