802. 区间和 【离散化】超详细解析
https://www.acwing.com/problem/content/804/
本题的数据范围实在太大，用哈希表做不出来，但是你会发现数轴上的数字是离散的，就是数轴上的数不是一个挨着一个的，数轴上的数并不是特别多。那么我们就可以将数轴上的点映射到一个挨着的数组里。
本解析一步步的求出结果，且根据案例。 故边看案例边看代码使用效果最好。
总共需要的数组
- add : 保存真实的下标和相应的值
- alls : 用来保存真实的下标和想象的下标的映射关系
- query : 用来保存我们查询的左右两个端点
- a : 保存想象的坐标所对应的值
- s: 保存想象的坐标所对应的值的前缀和
第一步: 输入数轴上所对应的值
for(int i=0;i<n;i++)
{
int index,x; cin>>index>>x;
add.push_back({index,x});//index 是我们真实的下标 x是数值
alls.push_back(index);// 将真实的下标和我们想象的坐标建立映射关系
}
第二步: 输入我们的查询的区间
for(int i=0;i<m;i++)
{
int l,r; cin>>l>>r;
query.push_back({l,r});//保存查询的区间
alls.push_back(l);
//将其左右端点也映射进来，目的是可以让我们在虚拟的映射表里找到，这对于我们后面的前缀和操作时是十分的方便的。
//如果当我们在虚拟的映射表里找的时候，如果没有找到左右端点，那么前缀和无法求。
alls.push_back(r);
}
第三步: 将虚拟的坐标排序并去重
为啥去重:
是因为当我们输入
3 5
3 6
即给数轴上3的点加5 再加 6时。此时我们的坐标映射表里有了两个3 3 但其实它们对应的是同一个坐标。
故需要去重，排序。
sort(alls.begin(), alls.end());//排序
alls.erase(unique(alls), alls.end());//去重(坐标)
那么此时，我们来看一下，案例所建立的映射表是怎样的。
第四步：根据真的坐标，来找到对应虚拟的坐标，将其位置加上其相对应的数值。
根据真的坐标找其对应的映射的坐标，用二分来查找。
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;// 因为要求前缀和，故下标从1开始方便，不用额外的再处理边界。
}
for(int i=0;i<add.size();i++)
{
int x=find(add[i].first);
a[x]+=add[i].second;
}
此时方框中的数，就是该位置所对应的值。
注意那些值为0的坐标是区间的边界，因为没有值的大小故为0。引入它们的目的是为了方便求前缀和。
最后一步: 求前缀和，根据我们的查询的区间来输出区间的和
for(int i=1;i<=alls.size();i++) s[i]=s[i-1]+a[i];
for(int i=0;i<query.size();i++)
{
int l=find(query[i].first),r=find(query[i].second);
cout<<s[r]-s[l-1]<<endl;
}
总的代码:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
typedef pair<int,int> PII;
const int N=300010;
int a[N],s[N];
vector<int> alls;
vector<PII> add,query;
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])
a[j ++ ] = a[i];
return a.begin() + j;
}
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(void)
{
int n,m; cin>>n>>m;
for(int i=0;i<n;i++)
{
int index,x; cin>>index>>x;
add.push_back({index,x});
alls.push_back(index);
}
for(int i=0;i<m;i++)
{
int l,r; 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), alls.end());//去重(坐标)
for(int i=0;i<add.size();i++)
{
int x=find(add[i].first);
a[x]+=add[i].second;
}
for(int i=1;i<=alls.size();i++) s[i]=s[i-1]+a[i];
for(int i=0;i<query.size();i++)
{
int l=find(query[i].first),r=find(query[i].second);
cout<<s[r]-s[l-1]<<endl;
}
return 0;
}
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 300010;
int a[N], s[N];
int n, m;
vector<int> alls;//坐标
vector<PII> add, query;// 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;
else l = mid + 1;
}
return r + 1;
}
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])
a[j ++ ] = a[i];
return a.begin() + j;
}
int main()
{
cin >> n >> m;
for(int i = 0; i < n; i ++ )
{
int x, c;
cin >> x >> c;
add.push_back({x, c});//保存真实的坐标和数值
alls.push_back(x);//保存映射的坐标
}
for(int i = 0; i < m; i ++ )
{
int l, r;
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), 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)
{
int l = find(item.first), r = find(item.second);
cout << s[r] - s[l - 1] << endl;
}
return 0;
}
#include<cstdio>
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;
map<int,int>mp,vis;// mp 映射值, vis 去重
int n,m;
vector<PII>ans;//
vector<int>all,sum;//总的下标
int find(int x)
{
int l=0,r=all.size()-1;
while(l<r)
{
int mid=l+r>>1;
if(x<=all[mid]) r=mid;
else l=mid+1;
}
return r+1;
}
int main(void)
{
cin>>n>>m;
while(n--)
{
int x,c; cin>>x>>c; mp[x]+=c;
if(!vis[x]) all.push_back(x),vis[x]++;
}
while(m--)
{
int l,r; cin>>l>>r;
ans.push_back({l,r});
if(!vis[l]) all.push_back(l),vis[l]++;
if(!vis[r]) all.push_back(r),vis[r]++;
}
sort(all.begin(),all.end());
sum.push_back(0);
for(int i=0;i<all.size();i++) sum.push_back(mp[all[i]]);
for(int i=1;i<sum.size();i++) sum[i]+=sum[i-1];
for(int i=0;i<ans.size();i++)
{
int l=find(ans[i].first);
int r=find(ans[i].second);
cout<<sum[r]-sum[l-1]<<endl;
}
return 0;
}
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
typedef pair<int,int> PII;
vector<int>sum,all;
vector<PII>ve;
map<int,int>mp,vis;
int n,m;
int find(int x)
{
int l=0,r=all.size()-1;
while(l<r)
{
int mid=l+r>>1;
if(all[mid]>=x) r=mid;
else l=mid+1;
}
return r+1;
}
int main(void)
{
cin>>n>>m;
while(n--)
{
int x,c; cin>>x>>c;
mp[x]+=c;
if(!vis[x]) all.push_back(x),vis[x]++;
}
while(m--)
{
int l,r; cin>>l>>r;
ve.push_back({l,r});
if(!vis[l]) all.push_back(l),vis[l]++;
if(!vis[r]) all.push_back(r),vis[r]++;
}
sort(all.begin(),all.end());
sum.push_back(0);
for(int i=0;i<all.size();i++) sum.push_back(mp[all[i]]),sum[i+1]+=sum[i];
for(int i=0;i<ve.size();i++)
{
int l=find(ve[i].first);
int r=find(ve[i].second);
cout<<sum[r]-sum[l-1]<<endl;
}
return 0;
}