AcWing 802：区间和 ← 离散化

【题目来源】
https://www.acwing.com/problem/content/804/

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

【输入格式】
第一行包含两个整数 n 和 m。
接下来 n 行，每行包含两个整数 x 和 c。
再接下来 m 行，每行包含两个整数 l 和 r。

【输出格式】
共 m 行，每行输出一个询问中所求的区间内数字和。

【数据范围】
−10^9≤x≤10^9,
1≤n,m≤10^5,
−10^9≤l≤r≤10^9,
−10000≤c≤10000

【输入样例】
3 3
1 2
3 6
7 5
1 3
4 6
7 8

【输出样例】
8
0
5

【算法分析】
★ 离散化：https://blog.csdn.net/hnjzsyjyj/article/details/143275575
离散化是一种数据处理的技巧，本质上可以看成是一种“哈希”，其保证数据在哈希以后仍然保持原来的“全/偏序”关系。用来离散化的可以是大整数、浮点数、字符串等等。

★ 离散化的本质，是映射。原理是将间隔很大的元素，映射到相邻的位置上，从而减少对空间的需求，也减少计算量。

★ C++ 中 for(auto i:v) 的用法
https://blog.csdn.net/hnjzsyjyj/article/details/132118215

【算法代码】

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
const int maxn=1e5+5;
int a[maxn],s[maxn];
int n,m;
vector<int> alls;
vector<PII> add,query;

int find(int x) { //discretization
    int le=0;
    int ri=alls.size()-1;
    while(le<ri) {
        int mid=(le+ri)>>1;
        if(alls[mid]>=x) ri=mid;
        else le=mid+1;
    }
    return ri+1;
}

int main() {
    cin>>n>>m;
    for(int i=0; i<n; i++) {
        int x,c;
        cin>>x>>c;
        alls.push_back(x);
        add.push_back({x,c});
    }

    for(int i=0; i<m; i++) {
        int le,ri;
        cin>>le>>ri;
        alls.push_back(le), alls.push_back(ri);
        query.push_back({le,ri});
    }

    //de-weight
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()), alls.end());

    for(auto v:add) {
        int x=find(v.first);
        a[x]+=v.second;
    }

    for(int i=1; i<=alls.size(); i++) {
        s[i]=s[i-1]+a[i]; //prefix sum
    }

    for(auto v:query) {
        int le=find(v.first);
        int ri=find(v.second);
        cout<<s[ri]-s[le-1]<<endl;
    }

    return 0;
}

/*
in:
3 3
1 2
3 6
7 5
1 3
4 6
7 8

out:
8
0
5
*/

【参考文献】
https://www.acwing.com/blog/content/2579/
https://www.acwing.com/solution/content/2321/
https://www.acwing.com/problem/content/solution/804/1/
https://blog.csdn.net/hnjzsyjyj/article/details/143275575