AcWing 802. 区间和
原题链接
简单
作者:
__43
,
2020-09-24 12:08:43
,
所有人可见
,
阅读 269
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int,int> PII;
vector<int> adds;
vector<PII> add,query;
const int N = 3e5 + 10;
int q[N],pre[N];
int find(int x)
{
int l = 0,r = adds.size() - 1;
while (l < r)
{
int m = l + (r - l) / 2;
if (adds[m] >= x) r = m;
else l = m + 1;
}
return l + 1;
}
int main(void)
{
int n,m;
scanf("%d%d",&n,&m);
while (n--)
{
int x,c;
scanf("%d%d",&x,&c);
adds.push_back(x);
add.push_back({x,c});
}
while (m--)
{
int l,r;
scanf("%d%d",&l,&r);
query.push_back({l,r});
adds.push_back(l);
adds.push_back(r);
}
sort(adds.begin(),adds.end());
adds.erase(unique(adds.begin(),adds.end()),adds.end());
for (auto i : add) q[find(i.first)] += i.second;
for (int i = 1;i <= adds.size();++i) pre[i] += pre[i - 1] + q[i];
for (auto i : query) printf("%d\n",pre[find(i.second)] - pre[find(i.first) - 1]);
return 0;
}