AcWing 802. 区间和
原题链接
简单
作者:
Karma
,
2019-10-23 08:59:33
,
所有人可见
,
阅读 686
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 大数和值
vector<pair<int, int>> san_val;
// 待查询的左边界和右边界
vector<pair<int, int>> cha;
// 所有点
vector<int> dian;
const int N = 3e5 + 10;
// 小数
vector<int> ju(N);
// 小数前缀和
vector<int> qzh(N);
// 大数映射为小数
int san_to_ju(int da)
{
int l = 0;
int r = dian.size();
while(l < r)
{
int mid = (l + r) >> 1;
if(dian[mid] >= da)
{
r = mid;
}
else
{
l = mid + 1;
}
}
// 此处查询到大数数组中的下标,
// 再 +1 偏移,
// 使小数下标从1开始,
// 便于之后的求前缀和
return l + 1;
}
int main()
{
int n, m;
cin >> n >> m;
// 存
for(int i = 0; i < n; ++ i)
{
int x, c;
cin >> x >> c;
san_val.push_back({x, c});
dian.push_back(x);
}
// 存
for(int i = 0; i < m; ++ i)
{
int l, r;
cin >> l >> r;
cha.push_back({l, r});
dian.push_back(l);
dian.push_back(r);
}
// 排序并去重
sort(dian.begin(), dian.end());
dian.erase(unique(dian.begin(), dian.end()), dian.end());
// 大数映射为小数
for(int i = 0; i < san_val.size(); ++ i)
{
int ind = san_to_ju(san_val[i].first);
ju[ind] = ju[ind] + san_val[i].second;
}
// 前缀和
for(int i = 1; i <= ju.size(); ++ i)
{
qzh[i] = qzh[i-1] + ju[i];
}
// 查询
for(int i = 0; i < cha.size(); ++ i)
{
int l = san_to_ju(cha[i].first);
int r = san_to_ju(cha[i].second);
int res = qzh[r] - qzh[l-1];
cout << res << endl;
}
}