离散化——区间和

题目描述

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

注释版代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=300010;//这里数组大小开300000是因为我们原数组，离散后的数组他最多就是l和r和x，每个数的范围是10^5,所以三个数就是3*10^5
vector<int> alls;//待离散化的位置暂存
typedef pair<int,int> PII;
vector<PII> query,add;
//因为输入的值后面还要进行离散化处理所以要存起来，又因为输入是两个两个的，所以用pair存起来
//两个操作，一个离散化后的数值输出，另一个是将c加到离散化后的x处
int a[N],s[N],b[N];//a[]表示原数组；b[]表示离散后的数组；s[]表示离散后的数组前缀和
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,x,c,l,r;
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d %d",&x,&c);
add.push_back({x,c});//存储准备将c加到离散后的x上去
alls.push_back(x);//x存储进alls准备离散
}
for(int i=1;i<=m;i++)
{
scanf("%d %d",&l,&r);
query.push_back({l,r});//l，r存储起来后面准备用
alls.push_back(l);
alls.push_back(r);//l和r放到alls里面准备离散
}
//为什么是x，l，r需要离散呢？
//因为离散不会对数值的相对大小发生改变，离散前大的，离散后也大，离散前小的，离散后也小
//为了验证x是不是在l和r之间，也就是说计算l-r之间的区间和的时候要不要加上x加上的那个c
//我们需要把l和r也离散后看看x是不是位于他们之间
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls.end()),alls.end());
//离散的方法：
//①排序 ②unique是把重复的元素都放到最后，并返回最后一个不重复的元素
//那么从最后一个不重复的元素的下一位一直到alls的最后end，都是重复的元素，于是我们用erase把这块元素擦掉即可
for(auto item:add)
{
int x=find(item.first);//将x离散
b[x]+=item.second;//b数组是离散后的数组，所以将c加到b[x]上
}
for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + b[i];//计算离散后数组的前缀和
for(auto item:query)                                     
{
l=find(item.first),r=find(item.second);//将l和r离散后
cout<<s[r]-s[l-1]<<endl;//即可计算l和r之间的区间和
}
return 0;
}         
 

原文地址：https://blog.csdn.net/r2931887650/article/details/142700741

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！