python/TangDou/AcWing/Discretization/802_2.cpp

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;

const int N = 300010; // 上限，n+2*m+10
int a[N];             // 映射后的数组
int s[N];             // a数组的前缀和数组

vector<int> alls;  // 坐标集合
vector<PII> add;   // 1、哪个位置，2：加上多少
vector<PII> query; // 1、开始点，2:结束点

int n, m;

/**
 * 功能：利用二分法查找原索引x的映射后索引值
 * 核心思路：原来是第几个是不变的，离散化后还是第几个,建立起了映射关系。
 * @param x 原来的索引号
 * @return 映射后小数组内的索引号
 */
int find(int x) {
    int l = 0, r = alls.size() - 1;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (alls[mid] >= x)
            r = mid;
        else
            l = mid + 1;
    }
    return l;
}
//	883 ms
int main() {
    // 输入数据
    cin >> n >> m;
    // 录入原始数据
    while (n--) {
        int x, c;
        cin >> x >> c;
        // 记录位置与值
        add.push_back({x, c});
        // 将位置记录到alls里
        alls.push_back(x);
    }
    // 读入查询范围
    int l, r;
    while (m--) {
        cin >> l >> r;
        // 要查的范围
        query.push_back({l, r});
        // 把要查询的点也分两次放入到坐标数组中
        alls.push_back(l), alls.push_back(r);
    }

    // 套路，排序+去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    // 生成a数组，每次都在映射后的坐标位置将值变大c
    for (int i = 0; i < add.size(); i++) {
        PII item = add[i];
        // find返回的是下标从0开始的位置，这里为了使用前缀和，要求a数据下标从1开始，有1个偏移量
        int x = find(item.first) + 1; // 映射为小范围的索引值
        a[x] += item.second;
    }

    // 预处理前缀和
    for (int i = 1; i < N; i++) s[i] = s[i - 1] + a[i];

    // 处理询问(前缀和应用)
    for (int i = 0; i < query.size(); i++) {
        PII item = query[i];
        // 根据原来的位置值，计算出映射后的位置值
        l = find(item.first) + 1;
        r = find(item.second) + 1;
        // 利用一维前缀和计算区间和
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}