题目描述

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

【题型提取】
给一些分得很开的数，对这些数进行操作

对策

把这些分得很开的数丢到一个小区间中紧密地挨着彼此，然后用前缀和/差分数组解决问题。
【注意】
需要映射的点不止是插入数值的点，还有查询操作的左右端点，因为这些点全都会被用到。

STL

对原始位置的排序去重操作可能大家会想到用set，但是set不支持用下标查找指定位置的元素，还需要遍历，所以我们采用vector排序，然后erase去重。

参考文献

y总视频

C++ 代码

#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
const int N = 3e5 + 10;//插入：一个坐标，查询：两个坐标，都是1e5，所以总共是3e5

int a[N], s[N];//a是插入数组，s是前缀和数组
int n, m;
typedef pair<int, int> PII;
vector<PII> add, query;
vector<int> alls;

int find(int x){//将所有涉及到的坐标映射到1~all.size()区间
    int l = 0, r = alls.size() - 1;
    while(l < r){
        int mid = l + r >> 1;
        if(alls[mid] >= x) r = mid;//为什么不用set？因为set无法利用下标获取指定位置元素值，在这一步会报错
        else l = mid + 1;
    }
    return l + 1;//或者r + 1（返回的是1，2，3...的下标，因为前缀和下标从1开始）
}

int main(){
    scanf("%d%d", &n, &m);
    while(n--){
        int x, c; scanf("%d%d", &x, &c);
        add.push_back({x,c});//为什么add的值要记录？因为要先等alls把元素全部加完，才能索引出正确的位置
        alls.push_back(x);
    }
    while(m--){
        int l, r; scanf("%d%d", &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());//vector的去重方法
    for(auto item : add){
        int x = find(item.first);
        a[x] += item.second;
    }
    for(int i = 1; i <= alls.size(); i++) s[i] = s[i-1] + a[i];
    for(auto item : query){
        int l = find(item.first), r = find(item.second);//记得l和r是find之后的下标
        printf("%d\n", s[r] - s[l-1]);
    }
    return 0;
}