离散化区间和 java c++

题面

题目链接：点击传送

假定有一个无限长的数轴，数轴上每个坐标上的数都是 0。
现在，我们首先进行 n 次操作，每次操作将某一位置 x 上的数加 c。
接下来，进行 m 次询问，每个询问包含两个整数 l 和 r，你需要求出在区间 [l,r] 之间的所有数的和。

解题思路

1. 将所有 增加数值的下标 和 需要查询区间的两端下标 存起来
2. 下标排序为增序
3. 4和5 建立 下标-值 键值对
4. 模拟增加过程，将 下标 对应的 键值 增加
5. 将查询模拟为增加 0 值
6. 前缀和操作
7. 查询，通过二分找到其对应下标，前缀和相减得到结果

java

import java.util.*;public class Main {public static int N = 300100;public static int[] s = new int[N];public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n =sc.nextInt(), m = sc.nextInt();int[][] query = new int[N/3][2];Map<Integer, Integer> mp = new TreeMap<>();for (int i = 1; i <= n; i ++ ) {int x = sc.nextInt(), y = sc.nextInt();mp.put(x, mp.getOrDefault(x, 0) + y);}for (int i = 1; i <= m; i ++ ) {int x = sc.nextInt(), y = sc.nextInt();query[i][0] = x;query[i][1] = y;mp.putIfAbsent(x, 0);mp.putIfAbsent(y, 0);}List<Integer> idx = new ArrayList<>(mp.keySet());for (int i = 0; i < idx.size(); i ++ ) s[i + 1] = s[i] + mp.get(idx.get(i));for (int i = 1; i <= m; i ++ ) {int l = find(idx, query[i][0]), r = find(idx, query[i][1]);System.out.println(s[r + 1] - s[l]);}}public static int find(List<Integer> idx, int x) {int l = 0, r = idx.size() - 1;while (l < r) {int mid = (l + r) >> 1;if (idx.get(mid) < x) l = mid + 1;else r = mid;}return r;}
}

cpp

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>using namespace std;
using LL = long long;
using PII = pair<int, int>;const int N = 3e5 + 10;int n, m;
LL a[N], pref[N];vector<int> idx;
vector<PII> add, query;int find(int k){int l =0, r=idx.size()-1;while(l < r){int mid = (l + r) >> 1;if(idx[mid] < k) l = mid + 1;else r = mid;}return r + 1;
} int main(){cin >> n >> m;for(int i=0; i<n; i++) {int x, k;cin >> x >> k;add.push_back({x, k});idx.push_back(x);}for(int i=0; i<m; i++) {int l, r;cin >> l >> r;query.push_back({l, r});idx.push_back(l);idx.push_back(r);}sort(idx.begin(), idx.end());idx.erase(unique(idx.begin(), idx.end()), idx.end());for(auto& p : add) {int x = find(p.first);a[x] += p.second;}for(int i=1; i<=idx.size(); i++) pref[i] += pref[i-1] + a[i];for(auto& p : query) {int l = find(p.first), r=find(p.second);cout << pref[r] - pref[l-1] << endl;}return 0;
}