题目

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

输入格式

• 第一行包含两个整数 $n $和 $m$。
• 接下来 $n$ 行，每行包含两个整数 $x $和 $c$。
• 再接下来$ m$ 行，每行包含两个整数 $l$ 和 $r$。

输出格式

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

本文题目：区间和

代码详解

$\huge \color{red}{离散化求区间和代码详解}$

• $find函数是实现离散化映射的关键$

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;    // 找到的是第一个 >=x 的数
        else    l = mid + 1;
    }
    return r +  1;  // 根据题意返回值，我们的映射从 1 开始
}

• $对 add 操作进行收集$

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

• $对 query 操作进行收集 $

    int l, r;
    for (int i = 0; i < m; i ++ ) {
        cin >> 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());

如果没有$unique$函数该怎么办？？

我们势必要自己去实现------$\color{red}{双指针思想}$

// 定义去重函数 unique

vector<int>::iterator unique(vector<int>& v) {
    int i, j;
    for (i = 0, j = 0; i < v.size(); i ++ ) {
        if(!i || v[i] != v[i - 1]) 
            v[j ++ ] = v[i];
    }
    // 从 0 ~ j-1 已去重
    return v.begin() + j;   // 返回已去重的右端点的下一个坐标
}

• $处理插入$

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

• $预处理前缀和$

$ for (int\space i\space =\space 1;\space i\space <=\space alls.size();\space i\space ++\space )\space\space\space s[i]\space =\space s[i - 1]\space +\space a[i];$

• $处理查询$

    for (auto item : query) {
        // 实际作用的是 alls 映射后的单元
        int r = find(item.second), l = find(item.first);
        cout << s[r] - s[l - 1] << endl;
    }

$\huge \color{blue}{完整代码：}$

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PA;

const int N = 3e5 + 10;
int a[N], s[N];     // s[] 为 a[] 的前缀和

vector<int> alls;
vector<PA> add, query;

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;    // 找到的是第一个 >=x 的数
        else    l = mid + 1;
    }
    return r +  1;  // 根据题意返回值，我们的映射从 1 开始
}

int main()
{
    int n, m;
    cin >> n >> m;
    
    // 对 add 操作进行收集
    int x, c;
    for (int i = 0; i < n; i ++ ) {
        cin >> x >> c;
        alls.push_back(x);
        add.push_back({x, c});
    }

    // 对 query 操作进行收集    
    int l, r;
    for (int i = 0; i < m; i ++ ) {
        cin >> 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());
    
    // 处理插入
    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) {
        // 实际作用的是 alls 映射后的单元
        int r = find(item.second), l = find(item.first);
        cout << s[r] - s[l - 1] << endl;
    }
    
    return 0;
}