思路

和普通的区间和有什么不一样？

数的范围很大，但是给的值有很少，很稀疏，需要离散化映射到小的下标范围
那么离散化的对象是哪些？ 离散化后的值怎么计算？

核心思路 ：映射后的下标范围是什么，映射后的坐标上有什么数，再求对应区间的和

收集待映射下标 -> 去重 -> 映射并参与相关操作（如给相应坐标赋值） -> 查询某种要求

• 首先要把映射的下标都收集起来 放到vector<int> alls
• alls中可能重复，则排序后去重
• 映射函数find() 映射范围为 0 ~ all.size() -1 这里加1 则映射的1 ~ all.size(),便于求前缀和
• 求映射后[l, r]的区间和
• 所以我们需要记录 操作add 询问query 前缀和s[N] 带映射的下标alls 映射后的坐标上操作后的数a[N]

收获

数组去重模板

vector<int> alls;
sort(alls.begin(), alls.end());
alls.erase(unique(all.begin(), all.end()), all.end());

unique（）的自我实现

// 返回类型为迭代器 去重后最后的位置
vector<int> :: iterator uqique(vector<int> &a)
{
    int j = 0;
    for(int i = 0; i < a.size(); i++)
    {
        if(!i || a[i] != a[i++])
            a[j ++] = a[i]
            // 其实是 a[j] = a[i]; j++;
    }

    return a.begin() + j;
}

c++ 代码

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

using namespace std;

typedef pair<int, int> PII;

const int  N = 300010; // 【坑2】为什么开这么大

int n, m;
int a[N], s[N];  // a离散化后的坐标上对应的数组 ， S为其前缀和

vector<int> alls;  // 所有待离的下标 
vector<PII> add, query; // 操作  和 查询|询问

int find(int x) //求 下标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 r + 1;
}

int main()
{
    cin >> n >> m;

    for(int i = 0; i < n; i++)
    {
        int x, c; // 在 x 上 加 c
        cin >> x >> c;
        add.push_back({x, c}); // 处理操作

        alls.push_back(x); //把下标加入待离散alls
    }

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

        alls.push_back(l); //把下标加入待离散alls
        alls.push_back(r); //把下标加入待离散alls

    }
    //把需要映射的下标排好序去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    // 处理插入 映射后下标对应的值
    for(auto item : add)
    {
        int x = find(item.first); // 映射
        a[x] += item.second; // 离散化后的坐标加上该加的数
    }
    // 处理前缀和
    for(int i = 1; i <= alls.size(); i++)  //【坑1】 从1开始 注意 <= 
        s[i] = s[i - 1] + a[i];

    // 处理询问
    for(auto item : query)
    {
        int l = find(item.first);
        int r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }

    return 0;
}