离散化 C++

题目

在这里插入图片描述

解题思路

将所有对坐标的访问用map映射到一个新的坐标轴上
再在新的坐标轴上进行加法
用前缀和快速求出区间的和

代码实现

#include<iostream>
#include<algorithm>
#include<unordered_map>using namespace std;typedef pair<int, int> PII;const int N = 1e6 + 10;//N开大一点，不然会有越界错误
int a[N], s[N];int main()
{int n, m;cin >> n >> m;vector<PII> add, query;//add存对坐标加法的行为， query存求区间和的请求vector<int> alls;//alls存所有对坐标的访问for (int i = 0; i < n; i ++ ){int x, plus;scanf("%d%d", &x, &plus);alls.push_back(x);add.push_back({x, plus});}for (int i = 0; i < m; i ++ ){int l, r;scanf("%d%d", &l, &r);alls.push_back(l); alls.push_back(r);query.push_back({l, r});}unordered_map<int, int> map;//map用来将alls中所有被访问的坐标映射到新的坐标上sort(alls.begin(), alls.end());//排序后才能达到有序映射的效果alls.erase(unique(alls.begin(), alls.end()), alls.end());//去重for (int i = 0; i < alls.size(); i ++ ){map[alls[i]] = i;//开始映射}for (int i = 0; i < add.size(); i ++ ){//在新坐标轴上做加法int idx = map[add[i].first], plus = add[i].second;a[idx] += plus;}//前缀和for (int i = 0; i < alls.size(); i ++ ){if (i == 0){s[i] = a[i];continue;}s[i] = s[i - 1] + a[i];}for (int i = 0; i < query.size(); i ++ ){int l = map[query[i].first], r = map[query[i].second];printf("%d\n", s[r] - s[l - 1]);}return 0;
}