01_区间和 interval_sum

离散化

把无限空间中有限个体映射到有限空间，以此提高算法的时空效率
例: 原数据：1,999,100000,15,
    处理后：1,3,4,2；
    原数据：{100,200}，{20,50000}，{1,400},
    处理后：{3,4}，{2,6}，{1,5}

步骤:
1、排序
2、去除重复元素（存在集合中，集合是不可能有重复元素的）
3、映射

补充: unique函数的实现

// unique函数: 把所有重复元素排到最后，最后返回的是指向重复元素的起始位置的迭代器
vector<int>::iterator unique(vector<int> &a) {
    int j = 0;
    for (int i = 0; i < a.size(); i++) {
        if (!i || a[i] != a[i - 1]) {
            a[j++] = a[i];
        }
    }
    return a.begin() + j;
}

（1）用 unordered_map 作映射

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

/*
300010: 所有可能访问的下标数量: 
add加数操作时访问的下标数量: 10^5
query查询操作时访问的下标数量: 10^5 * 2（l 和 r）
*/
const int N = 300010;
int n, m;

vector<int> all_pos;                // 所有要访问的下标
unordered_map<int, int> pos_map;    // 真（长）下标映射成假（短）下标，比 map 快
vector<PII> add, query;             // 分别存储加数操作(x, c)和查询操作(l, r)两个元素之间的下标关系
int a[N], s[N];                     // 存储所有下标的数值，前缀和

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int x, c;
        cin >> x >> c;

        all_pos.push_back(x);
        add.push_back({x, c});
    }

    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;

        all_pos.push_back(l);
        all_pos.push_back(r);
        query.push_back({l, r});
    }

    sort(all_pos.begin(), all_pos.end()); // 排序
    /*
    剔除重复元素
    unique函数: 把所有重复元素排到最后，最后返回的是指向重复元素的起始位置的迭代器
    */
    all_pos.erase(unique(all_pos.begin(), all_pos.end()), all_pos.end());

    // 映射: 真下标映射假下标
    for (int i = 0, j = 1; i < all_pos.size(); i++) {
        // 映射的假下标 j 从 1 开始: 因为之后算前缀和需要从 1 开始
        pos_map[all_pos[i]] = j++;
    }

    // 加数操作
    for (auto it : add) {
        int i = pos_map[it.first];  // 真下标映射得到假下标
        a[i] += it.second;          // 加数
    }

    // 计算前缀和
    for (int i = 1; i <= all_pos.size(); i++) s[i] = s[i - 1] + a[i];

    // 查询操作
    for (auto it : query) {
        int l = pos_map[it.first], r = pos_map[it.second];  // 真下标映射得到假下标
        cout << s[r] - s[l - 1] << endl;                    // 算区间和
    }

    return 0;
}

（2）用二分实现映射函数作映射

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 300010;
int n, m;

vector<int> all_pos;
vector<PII> add, query;
int a[N], s[N];

// 映射: 通过真下标得到假下标，用二分查找
int mapping(int x) {
    int l = 0, r = all_pos.size() - 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (all_pos[mid] < x) l = mid + 1;
        else r = mid;
    }
    return l + 1; // 加 1 是映射下标从 1 开始: 因为之后算前缀和需要从 1 开始
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int x, c;
        cin >> x >> c;

        all_pos.push_back(x);
        add.push_back({x, c});
    }

    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;

        all_pos.push_back(l);
        all_pos.push_back(r);
        query.push_back({l, r});
    }

    sort(all_pos.begin(), all_pos.end());
    all_pos.erase(unique(all_pos.begin(), all_pos.end()), all_pos.end());

    // 加数操作
    for (auto it : add) {
        int i = mapping(it.first);  // 真下标映射得到假下标
        a[i] += it.second;          // 加数
    }

    // 计算前缀和
    for (int i = 1; i <= all_pos.size(); i++) s[i] = s[i - 1] + a[i];

    // 查询操作
    for (auto it : query) {
        int l = mapping(it.first), r = mapping(it.second);  // 真下标映射得到假下标
        cout << s[r] - s[l - 1] << endl;                    // 算区间和
    }

    return 0;
}