题目描述

假定有一个无限长的数轴，数轴上每个坐标上的数都是0。

现在，我们首先进行 n 次操作，每次操作将某一位置x上的数加c。

接下来，进行 m 次询问，每个询问包含两个整数l和r，你需要求出在区间[l, r]之间的所有数的和。

样例

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

8
0
5

算法

(离散化)

主要来对代码中的变量进行一些解释，整体算法推荐看y总的视频来理解

1. vector<int> alls，这个alls数组中存储的值是离散化之前的坐标值，也就是题目中的x, l, r，alls数组的下标则是离散化后的原先下标的新的映射值，数据范围在$10^5$内的a[k]对应的下标值k。
2. 简而言之，我们离散化的是下标，并不是原先下标中存储的数值，也就是c。
3. add和query，存储的是原先的大数据范围的下标和存储值，需要配合find()函数一起使用，find()的作用是通过大数据范围中的下标值x, l, r，在alls数组中寻找x, l, r对应的下标，因为在alls数组中，x, l, r并不是作为数组的下标，而是数组中存储的值。通过find()函数可以找到x, l, r离散化后映射到了新的下标，因为find()函数用到了二分，二分的范围是0~alls.size() - 1，也就是说，原先大数据范围有多少个下标被赋值了，alls.size()就有多大，这道题样例中，alls.size()是6。所以原先可能很大的下标0, 100, 2000, 900000就被映射到了0, 1, 2, 3。
4. 我犯了哪些错呢？计算前缀和的时候，一开始没明白为什么是i <= alls.size()，现在明白了，因为a[k]中的k，就是find()函数返回的alls数组的下标，所以a[k]数组的范围就是0 ~ alls.size() - 1，所以要用i <= alls.size()。

   • 因为我们是将原来的大数据范围映射到了1 ~ alls.size()，所以也可以这样理解。

5. 其他，就是一开始对add和query不太熟悉，写得少吧。
6. Happy coding!

时间复杂度

$O(n + 2m)$

C++ 代码

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

using namespace std;

const int N = 300010;

typedef pair<int, int> PII;

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

int a[N], s[N];

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 l + 1;
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);

    while(n --)
    {
        int x, c;
        scanf("%d%d", &x, &c);
        add.push_back({x, c});

        alls.push_back(x);
    }

    while(m --)
    {
        int l, r;
        scanf("%d%d", &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 k = find(item.first);
        a[k] += item.second;
    }

    for(int i = 1; i <= alls.size(); i ++) s[i] = s[i - 1] + a[i];  // **1

    for(auto item : query)
    {
        int l = find(item.first);
        int r = find(item.second);
        printf("%d\n", s[r] - s[l - 1]);
    }

    return 0;
}

前缀和从0开始枚举的AC代码

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

using namespace std;

const int N = 300010;

typedef pair<int, int> PII;

vector<PII> add, query;
vector<int> alls;
int a[N], s[N];

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 l;
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);

    while(n --)
    {
        int x, c;
        scanf("%d%d", &x, &c);
        add.push_back({x, c});

        alls.push_back(x);
    }

    while(m --)
    {
        int l, r;
        scanf("%d%d", &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 k = find(item.first);
        a[k] += item.second;
    }

    for(int i = 0; i < alls.size(); i ++) s[i + 1] = s[i] + a[i];

    for(auto item : query)
    {
        int l = find(item.first);
        int r = find(item.second);
        printf("%d\n", s[r + 1] - s[l]);
    }

    return 0;
}

unique()函数的实现

1. 返回类型是vector<int>::iterator
2. 实现的本质是双指针
3. if(!i || a[i] != a[i - 1])中的第一个条件表示i是第一个元素
4. if(!i || a[i] != a[i - 1])中的第二个条件表示当前元素和前一个元素不一样，因为是去重
5. 符合条件就执行a[j ++] = a[i]
6. 最后返回a.begin() + j，j表示所有不同元素的长度，所以从头加j，就是不同元素的区间。

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

using namespace std;

const int N = 300010;

typedef pair<int, int> PII;

vector<PII> add, query;
vector<int> alls;
int a[N], s[N];

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 l;
}

vector<int>::iterator unique(vector<int> &a)
{
    int j = 0;
    for(int i = 0; i < a.size(); i ++)
        // if(!i && a[i] != a[i - 1])
        if(!i || a[i] != a[i - 1])
            a[j ++] = a[i];               // a[0]~a[j - 1]是所有a中不重复的数

    return a.begin() + j;
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);

    while(n --)
    {
        int x, c;
        scanf("%d%d", &x, &c);
        add.push_back({x, c});

        alls.push_back(x);
    }

    while(m --)
    {
        int l, r;
        scanf("%d%d", &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());
    alls.erase(unique(alls), alls.end());

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

    for(int i = 0; i < alls.size(); i ++) s[i + 1] = s[i] + a[i];

    for(auto item : query)
    {
        int l = find(item.first);
        int r = find(item.second);
        printf("%d\n", s[r + 1] - s[l]);
    }

    return 0;
}