AcWing 802. 区间和
原题链接
简单
作者:
U3dever
,
2024-04-18 20:52:26
,
所有人可见
,
阅读 2
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
constexpr int N = 300010;
int q[N], s[N];
vector<int> alls;
vector<pair<int ,int>> add, query;
int find(int x)
{
int l = 0, r = (unsigned int)alls.size() - 1;
while (l < r)
{
int mid = (l + r + 1) >> 1;
if (alls[mid] <= x) l = mid;
else r = mid - 1;
}
return l + 1;
}
class IntervalSum
{
public:
static void quick_sort(std::vector<int>::iterator begin, std::vector<int>::iterator end)
{
if (begin >= end) return ;
int mid = (end - begin) >> 1;
int pivot = *(begin + mid);
std::vector<int>::iterator lit = begin - 1, rit = end + 1;
while (lit <= rit)
{
do { lit++; } while (*lit < pivot);
do { rit--; } while (*rit > pivot);
if (lit < rit) std::swap(*lit, *rit);
}
quick_sort(begin, lit - 1), quick_sort(lit, end);
}
static std::vector<int>::iterator unique_sorted(std::vector<int> &vec)
{
decltype(vec.size()) j = -1;
for (decltype(vec.size()) i = 0; i < vec.size(); i++)
if (i && vec[i] != vec[i - 1])
vec[++j] = vec[i];
return vec.begin() + j;
}
};
int main()
{
int n, m;
cin >> n >> m;
int x, y;
for (int i = 0; i < n; i++)
{
cin >> x >> y;
add.push_back({x, y});
alls.push_back(x);
}
for (int j = 0; j < m; j++)
{
cin >> x >> y;
query.push_back({x, y});
alls.push_back(x), alls.push_back(y);
}
IntervalSum::quick_sort(alls.begin(), alls.end() - 1);
//alls.erase(IntervalSum::unique_sorted(alls), alls.end());
//alls.erase(unique(alls.begin(), alls.end()), alls.end());
for (auto item : add)
q[find(item.first)] += item.second;
for (int i = 1; i <= alls.size(); i++)
s[i] = s[i - 1] + q[i];
for (auto item : query)
{
int l = find(item.first), r = find(item.second);
cout << s[r] - s[l - 1] << endl;
}
return 0;
}