题目链接:https://www.acwing.com/problem/content/description/804/
时/空限制：2s / 64MB

题目描述

假定有一个无限长的数轴，数轴上每个坐标上的数都是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

解题思路

题意:首先进行n次操作，将某一位置x上的数加c。然后进行m次询问求出在区间[l, r]之间的所有数的和。
思路:因为存储的下标实在太大了，如果直接开这么大的数组，根本不现实，还有就是数轴，要是采用下标的话，可能存在负值，所以也不能，如果用哈希表的话，我们可能需要从-1e9遍历到1e9，因为哈希表不能排序，所以我们一般不能提前知道哪些数轴上的点存在哪些不存在，所以一般是从负的最小值到正的最大值都枚举一遍，时间复杂度太高，所以就要离散化。

离散化的本质，是映射，将间隔很大的点，映射到相邻的数组元素中。减少对空间的需求，也减少计算量。

所以我们首先可以对坐标进行离散化，然后再根据离散化后的下标来进行前缀和，然后就可以输出区间[l, r]之间的和了。

Accepted Code:

/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int hash_[MAXN << 2], bits[MAXN << 2];
struct Hash {
    int l, r;
}Q[MAXN], p[MAXN];
int main() {
    int n, m, cnt = 0;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) {
        int x, c;
        scanf("%d%d", &p[i].l, &p[i].r);
        hash_[cnt++] = p[i].l;
    }
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &Q[i].l, &Q[i].r);
        hash_[cnt++] = Q[i].l;
        hash_[cnt++] = Q[i].r;
    }
    sort(hash_, hash_ + cnt);//排序
    cnt = unique(hash_, hash_ + cnt) - hash_;//去重
    for (int i = 0; i < n; i++) {
        int x = lower_bound(hash_, hash_ + cnt, p[i].l) - hash_;//映射
        bits[x] += p[i].r;
    }
    for (int i = 1; i < cnt; i++)
        bits[i] += bits[i - 1];
    for (int i = 0; i < m; i++) {
        int l = lower_bound(hash_, hash_ + cnt, Q[i].l) - hash_;
        int r = lower_bound(hash_, hash_ + cnt, Q[i].r) - hash_;
        printf("%d\n", bits[r] - bits[l - 1]);
    }
    return 0;
}