19.Acwing基础课第802题-简单-区间和

19.Acwing基础课第802题-简单-区间和

题目描述

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

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

共 m 行，每行输出一个询问中所求的区间内数字和。
数据范围

−109≤x≤109
1≤n,m≤100000，
−109≤li≤ri≤109
−10000≤c≤10000
输入样例：

1. 3 3
2. 1 2
3. 3 6
4. 7 5
5. 1 3
6. 4 6
7. 7 8

复制代码

输出样例：

1. 8
2. 0
3. 5

复制代码

代码：

[code]#include #include #include using namespace std;typedef pair PII;const int N = 300010;//开30万是因为插入操作总数是10万（插入操作里1个坐标），查询操作是10万（查询操作两个坐标）int n, m;int a[N], s[N];//数组a[N]为新映射下标对应的数，s[N]为前缀和vector alls;//alls保存所要操作的下标vector add, query;//add存插入的值，query用来存将来要查询的左右边界的离散化前的下标//求x的值离散化后的结果int find(int 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;//把数值映射到从1开始的数组里}int main(){    cin >> n >> m;    for (int i = 0; i < n; i++)    {        int x, c;        cin >> x >> c;        add.push_back({ x, c });//下标x的位置加c        alls.push_back(x);//下标x离散化，先把x加到待离散化的数组里面去    }    for (int i = 0; i < m; i++)//读入所有区间的左右端点    {        int l, r;        cin >> l >> r;        query.push_back({ l, r });        alls.push_back(l);//读入所有区间的左右端点加到待离散化的数组里去        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