题目描述

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

离散化

首先定义一个结构体，用来保存索引和累加值

typedef struct{
    int nun, value;
}PII;

然后按照结构体数组的索引值进行排序、去重

去重的同时把累加值加起来

然后定义另一个数组，预处理前缀和

最后处理$m$次询问，每次读入$l,r$，

然后分别求出数组中索引值小于等于$l$的最大值的下标，和大于等于$r$的最小值的下标

为了前缀和和二分返回的结果方便所以数组下标从1开始

时间复杂度分析：

• 快排$O(nlogn)$
• 去重$O(n)$
• 前缀和$O(n)$
• $m$次询问二分$O(mlogn)$

$300ms$

C语言代码

时间复杂度$O(mlogn)$

#include<stdio.h>
#define N 100010

typedef struct{
    int num;
    int value;
}PII;

PII a[N];
int b[N], n, m;

void quick_sort(int l, int r)
{
    if(l >= r)  return;

    int i = l - 1, j = r + 1, x = a[l].num;
    while(i < j)
    {
        do i ++; while(a[i].num < x);
        do j --; while(a[j].num > x);

        if(i < j)
        {
            PII t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }

    quick_sort(l, j);
    quick_sort(j + 1, r);
}

int findl(int x)            //返回大于等于x的最小值
{
    int l = 1, r = n;
    while(l < r)
    {
        int mid = (l + r) >> 1;
        if(a[mid].num >= x)
            r = mid;
        else
            l = mid + 1;
    }
    if(x <= a[l].num)
        return l;
    else
        return n + 1;       //x超过最大值
}

int findr(int x)            //返回小于等于x的最大值
{
    int l = 1, r = n;
    while(l < r)
    {
        int mid = (l + r + 1) >> 1;
        if(a[mid].num <= x)
            l = mid;
        else
            r = mid - 1;
    }

    if(x >= a[l].num)
        return l;
    else
        return 0;           //x小于最小值
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i ++)  scanf("%d%d", &a[i].num, &a[i].value);

    quick_sort(1, n);                       //快速排序

    int j = 1;
    for(int i = 2; i <= n; i ++)            //双指针原地去重
    {
        if(a[i].num == a[j].num)
            a[j].value += a[i].value;
        else
            a[++ j] = a[i];
    }
    n = j;

    //for(int i = 1; i <= n; i ++)  printf("%d %d %d\n", i, a[i].num, a[i].value);

    for(int i = 1; i <= n; i ++)  b[i] = b[i - 1] + a[i].value;     //前缀和
    while(m --)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        l = findl(l), r = findr(r);
        printf("%d\n", b[r] - b[l - 1]);
    }

    return 0;
}

C++ 代码

#include<cstdio>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 400010;

vector<int> v;
int find(int x)
{
    return lower_bound(v.begin(), v.end(), x) - v.begin();
}

int n, m;
int x[N], c[N];
int l[N], r[N];
int sum[N];

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i ++)
    {
        scanf("%d%d", &x[i], &c[i]);
        v.push_back(x[i]);
    }
    for(int i = 0; i < m; i ++)
    {
        scanf("%d%d", &l[i], &r[i]);
        v.push_back(l[i]);
        v.push_back(r[i]);
    }
    v.push_back(-2e9);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());

    for(int i = 0; i < n; i ++)  sum[find(x[i])] += c[i];

    n = v.size() - 1;
    for(int i = 1; i <= n; i ++)  sum[i] += sum[i - 1];

    for(int i = 0; i < m; i ++)
        printf("%d\n", sum[find(r[i])] - sum[find(l[i]) - 1]);
    return 0;
}