题目描述
假定有一个无限长的数轴,数轴上每个坐标上的数都是0。
现在,我们首先进行 n 次操作,每次操作将某一位置x上的数加c。
接下来,进行 m 次询问,每个询问包含两个整数l和r,你需要求出在区间[l, r]之间的所有数的和。
输入格式
第一行包含两个整数n和m。
接下来 n 行,每行包含两个整数x和c。
再接下里 m 行,每行包含两个整数l和r。
输出格式
共m行,每行输出一个询问中所求的区间内数字和。
数据范围
$-10^9\leq x\leq 10^9$
$1\leq n,m\leq 10^5$
$-10^9\leq l,r\leq 10^9$
$-10^4\leq c\leq 10^4$
输入样例
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例
8
0
5
看到求区间和,一下想到了 前缀和 ,用s[x]
表示x之前的数的和就可以了,以值为下标但是这道题x的值域太大,会MLE
我们使用一个新的科技: 离散化
还是前缀和的思想,不过是把 s 数组里面的元素映射到几个比较小的值上面
用几个数字就开多大的 s 数组, n 和 m 的值较小,就不会MLE啦
怎么映射
我们可以用一个数组 num
,存下来每个用到的数字
原来我们用 s[x] 表示小于等于x的和,现在我们在num里面二分出x,把下标记作t
,此时就可以用s[t]代替原来的s[x]廖!
记录数字后要排个序+判个重
Time: $\mathcal{O}((n+m)log_2n)$
Code:
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int n, m;
int s[3*N];
int num[3*N];
pair<int, int> query[N], add[N];//要先记录数字,所以得玩离线的,先存下操作
int idx_num, idx_add, idx_query;
int find(int x)//二分
{
int l = 1,r = idx_num;
while(l<r)
{
int mid = l+r>>1;
if(num[mid]<x) l = mid+1;
else r = mid;
}
return l;
}
int main()
{
cin >> n >> m;
for(int i = 1; i<=n; i++)
{
int x, c;
cin >> x >> c;
num[++idx_num] = x;
add[++idx_add] = {x, c};
}
for(int i = 1; i<=m; i++)
{
int l,r;
cin >> l >> r;
num[++idx_num] = l, num[++idx_num] = r;
query[++idx_query] = {l,r};
}
//排序+判重
sort(num+1, num+idx_num+1);
idx_num = unique(num+1, num+idx_num+1)-num-1;
for(int i = 1; i<=idx_add; i++)
{
int t = find(add[i].first);
s[t] += add[i].second;//前缀和
}
for(int i = 1; i<=idx_num; i++) s[i] += s[i-1];
for(int i = 1; i<=idx_query; i++)
{
int l = find(query[i].first),r = find(query[i].second);
cout << s[r]-s[l-1] << endl;//直接用s[r]-s[l-1]表示普通的(MLE)s[query.first]-s[query.second-1]
}
return 0;
}