题目描述
假定有一个无限长的数轴,数轴上每个坐标上的数都是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
算法
(离散化和前缀和) O((n+2∗m)log(n+2∗m))
思路
首先为什么要使用离散化(可以对应数学上的映射关系,直白讲就是换一种表现方式),而不是哈希。(Hash一般用于字符串的处理,并且哈希不能处理排序和缩小数组空间)
为什么使用了3个vector数组?
1.alls的作用是记录所有数组下标的作用(这里的下标去重排序,映射的结果)
2.add的作用是记录数组下标和添加的数值(要映射的数据)
3.query的作用是把要处理的数组储存起来(处理区间和相加)
为什么要排序和去重?
1.排序是为了更好的去重
2.去重的条件:第一个或者相邻之间不等
本题中的注意
1.前缀和从1开始
2.注意逻辑顺序
C++ 代码
#include <iostream>
#include <algorithm>
#include <vector>
//#include <cstdio>
using namespace std;
const int L=3e5+10;
typedef pair<int,int> PR;
int p[L],s[L];
vector <int> alls;
vector<PR> add,query;
int m,n;
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)/2;
if(alls[mid]<=x) l=mid;
else r=mid-1;
}
return r+1;
}
int main ()
{
cin>>n>>m;
while(n--)
{
int x,c;
cin>>x>>c;
alls.push_back(x);
add.push_back({x,c});
}
while(m--)
{
int l,r;
cin>>l>>r;
alls.push_back(l);
alls.push_back(r);
query.push_back({l,r});
}
sort(alls.begin(),alls.end());
alls.erase(unique(alls),alls.end());
for(auto it:add)
{
int x=find(it.first);
p[x]+=it.second;
}
for(int i=1;i<=alls.size();i++) s[i]=s[i-1]+p[i];
for(auto it:query)
{
int l=find(it.first),r=find(it.second);
cout<<s[r]-s[l-1]<<endl;
}
return 0;
}
欢迎讨论