题目描述:
假定有一个无限长的数轴,数轴上每个坐标上的数都是 0。
现在,我们首先进行 n 次操作,每次操作将某一位置 x 上的数加 c。
接下来,进行 m 次询问,每个询问包含两个整数 l 和 r,你需要求出在区间 [l,r] 之间的所有数的和。
输入格式
第一行包含两个整数 n 和 m。
接下来 n 行,每行包含两个整数 x 和 c。
再接下来 m 行,每行包含两个整数 l 和 r。
输出格式
共 m 行,每行输出一个询问中所求的区间内数字和。
数据范围
−1e9≤x≤1e9,
1≤n,m≤1e5,
−1e9≤l≤r≤1e9,
−10000≤c≤10000
输入样例:
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例:
8
0
5
离散化
离散化,把无限空间中有限的个体映射到有限的空间中去,以此提高算法的时空效率。
通俗的说,离散化是在不改变数据相对大小的条件下,对数据进行相应的缩小。例如:
原数据:1,999,100000,15;处理后:1,3,4,2;(常考)
原数据:{100,200},{20,50000},{1,400};处理后:{3,4},{2,6},{1,5};
简单来说就是:
对于值域大,个数少的数据,某些题以这些值为下标,但不能开长度为如1e9的数组,
因此要将其映射到从0开始的自然数。
总结:离散化的原因:
一是因为存储的下标实在太大了,如果直接开这么大的数组,根本不现实;
第二个原因,本文是数轴,要是采用下标的话,可能存在负值,所以也行不通。
注:
哈希表也是不可以的,因为哈希表不能像离散化那样缩小数组的空间,导致我们可能需要从-e9遍历到1e9,
因为哈希表不能排序,所以我们一般不能提前知道哪些数轴上的点存在哪些不存在,所以一般是从负的最小值
到正的最大值都枚举一遍,时间复杂度太高,于是就有了本题的离散化。
注:
(1)a[N]中或有重复元素:去重
(2)如何算出a[i]离散化后的值:二分
映射关系:
映射最大的难点是前后的映射关系,如何能够将不连续的点映射到连续的数组的下标。
此处的解决办法就是开辟额外的数组存放原来的数组下标,本文是原来上的数轴上的非连续点的横坐标。
此处的做法是是对原来的数轴下标进行排序,再去重。
去重原因:
因为本题提前考虑了前缀和的思想,就是我们需要求出的区间内的和的两端端点不一定有元素,
提前加如需要求前缀和的两个端点,有利于我们进行二分搜索,其实二分搜索里面我们一般假定有解的,
如果没解的话需要特判,所以提前加入了这些元素,从而导致可能出现重复元素。
所以要去重。
数组空间:
const int N=3e5+10;
因为时间复杂度是O(n+2m),1≤n,m≤1e5 ,
有n次操作,前缀和最多耗费O(2m)。
所以时间复杂度:(离散化) O((n+2∗m)log(n+2∗m))
离散化模板:
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素
// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于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; // 映射到1, 2, ...n
//返回r +1,这是变相的让映射后的数组从1开始。此处描述映射后的数组下标对应的数值用的是a数组
}
C++ pair函数
pair 默认对first升序,当first相同时对second升序;
类模板:template <class T1, class T2> struct pair
参数:T1是第一个值的数据类型,T2是第二个值的数据类型。
功能:pair将一对值组合成一个值,这一对值可以具有不同的数据类型(T1和T2),
两个值可以分别用pair的两个公有函数first和second访问。
具体用法:
1.定义(构造):
pair<int, double> p1; //使用默认构造函数
pair<int, double> p2(1, 2.4); //用给定值初始化
pair<int, double> p3(p2); //拷贝构造函数
2.访问两个元素(通过first和second):
pair<int, double> p1; //使用默认构造函数
p1.first = 1;
p1.second = 2.5;
cout << p1.first << ' ' << p1.second << endl;
C++版:
#include<iostream>
#include<vector>//java:ArrayList
#include<algorithm>
using namespace std;
typedef pair<int,int> PII;//C++ pair函数
const int N=3e5+10;
int n,m;
int a[N];//存的映射后的连续的数
int s[N];//前缀和
vector<int> alls;//存储所有待离散化的值
vector<PII> add,query;//增加,查询两操作
//二分求出x对应的离散化的值
int find(int x)//找到第一个大于等于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;//映射到1,2...n
}
//C++的unique函数实现原理(java等可参考思路)
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];
//a[0]~a[j-1]为所有a中不重复的数
}
return a.begin()+j;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
{
int x,c;
scanf("%d %d",&x,&c);
add.push_back({x,c});//相当于hashmap,将n 次操作存入add,每次将 x 上的数加 c。
alls.push_back(x);//因为要将x离散化,所以将x加入待离散化的alls数组末尾
}
for(int i=0;i<m;i++)
{
int l,r;
scanf("%d %d",&l,&r);
query.push_back({l,r});//存入m 次询问,求出在区间 [l,r] 之间的所有数的和。
//区间左右端点都需要离散化,所以将其加入待离散化数组
alls.push_back(l);
alls.push_back(r);
}
//此时已将所有需要用的下标加入到了alls里面
//去重
sort(alls.begin(),alls.end());//将所有值排序
// printf("排序后的alls: ");
// for(int i=0;i<alls.size();i++) printf("%d ",alls[i]);
alls.erase(unique(alls.begin(),alls.end()),alls.end());//去掉重复元素
// printf("去重后的alls: ");
// for(int i=0;i<alls.size();i++) printf("%d ",alls[i]);printf("\n");
//此时,alls数组升序且不重复:
for(auto item:add) //进行n次add操作:{x,c}集,在某一位置 x 上的数加 c。
{
int x=find(item.first);
a[x]+=item.second;
}
//printf("\n");
//区间[l,r]前缀和
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);
printf("%d\n",s[r]-s[l-1]);
}
return 0;
}
Java版: