基础算法复习:离散化
题目描述
假定有一个无限长的数轴,数轴上每个坐标上的数都是0。
现在,我们首先进行 n 次操作,每次操作将某一位置x上的数加c。
接下来,进行 m 次询问,每个询问包含两个整数l和r,你需要求出在区间[l, r]之间的所有数的和。
输入格式
第一行包含两个整数n和m。
接下来 n 行,每行包含两个整数x和c。
再接下里 m 行,每行包含两个整数l和r。
输出格式
共m行,每行输出一个询问中所求的区间内数字和。
数据范围
−109≤x≤109,
1≤n,m≤105,
−109≤l≤r≤109,
−10000≤c≤10000
样例
输入样例:
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例:
8
0
5
审题
问题情景是要我们求区间和,第一反应可能是直接利用前缀和来求。然而看看数据范围,x的跨度非常大,如果要用前缀和来求,就需要开1e9这个数量级大小的数组,内存消耗是非常大的。并且,涉及到的数的个数的数量级只有1e5,分布比较稀疏,从而使用离散化来处理之后再结合前缀和来求才是可行的做法。
复习:离散化
[1]离散化,把无限空间中有限的个体映射到有限的空间中去,以此提高算法的时空效率。
通俗的说,离散化是在不改变数据相对大小的条件下,对数据进行相应的缩小。例如:
原数据:1,999,100000,15;处理后:1,3,4,2;
原数据:{100,200},{20,50000},{1,400};
处理后:{3,4},{2,6},{1,5};
问题求解
首先看看我们要处理哪些数据,一系列待插入的点位x,一系列待插入的值c,一系列区间左右端点,前缀和数组,离散化后的数组,待离散化的所有点。点位x和值c之间是一一配对的,左右端点也是一一配对的,因此我们用pair数组来存,待离散化的所有点也用一个vector数组来存。读入数据后进行离散化(离散化主要步骤:排序,去重,求每个点离散化后对应的数。此处排序是要保持各个点离散化前后的顺序,去重是为了使每个点x唯一映射一个下标。)。最后再利用前缀和来处理询问即可。
参考文献
[1]百度百科:离散化
acwing 算法基础课 离散化模板
C++ 代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> alls;//所有待离散化的数
vector<pair<int,int>> add,interval;//存储add操作和询问的区间端点
const int N=300010;//最多会有1e5+2*1e5个数
int a[N],s[N];//存储操作后的值和前缀和
//找到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;
}
int main(){
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++){
int x,c;
scanf("%d %d",&x,&c);
add.push_back({x,c});
alls.push_back(x);
}
for(int i=0;i<m;i++){
int l,r;
scanf("%d %d",&l,&r);
interval.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:interval){
int l=find(item.first),r=find(item.second);
printf("%d\n",s[r]-s[l-1]);
}
return 0;
}