题目描述#include[HTML_REMOVED]
include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
const int N=3e6+1;
int a[N],s[N];int n,m;
vector[HTML_REMOVED]all;
vector[HTML_REMOVED]>add,query;
int find(int x)
{
int l=0;int r=all.size()-1;
while(l[HTML_REMOVED]>1;
if(all[mid]>=x)
r=mid;
else
l=mid+1;
}
return l+1;
}
int main()
{
scanf(“%d %d”,&n,&m);
for(int i=1;i<=n;i++)
{
int x,c;
scanf(“%d %d”,&x,&c);
add.push_back({x,c});
all.push_back(x);
}
for(int i=1;i<=m;i++)
{
int l,r;
scanf("%d %d",&l,&r);
query.push_back({l,r});
all.push_back(l);
all.push_back(r);
}
sort(all.begin(),all.end());
all.erase(unique(all.begin(),all.end()),all.end());
for(auto item :add)
{
int x=find(item.first);
a[x]+=item.second;
}
for(int i=1;i<=all.size();i++)
s[i]=s[i-1]+a[i];
for (auto item : query) {
int l = find(item.first);
int r = find(item.second);
printf("%d\n", s[r] - s[l-1]);
}
}
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla