本文共 1701 字，大约阅读时间需要 5 分钟。

题目链接:

时/空限制：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 
   
    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;}
   

转载地址：http://xybtf.baihongyu.com/