题目描述
假定有一个无限长的数轴,数轴上每个坐标上的数都是 0。
现在,我们首先进行 n 次操作,每次操作将某一位置 x 上的数加 c。
接下来,进行 m 次询问,每个询问包含两个整数 l 和 r,你需要求出在区间 [l,r] 之间的所有数的和。
离散化
解题思路
1.含义
这里指的是整数的离散化.且保序.(离散化后的映射保留原有次序)
一般应用场景:值域范围很大,如在1e9量级;而数值的个数相比很小,如在1e5的量级.
离散化:将值映射为从x开始的连续自然数.
举例:
原数组:-1010101 -8 0 77 2828282828 ->
离散化: 0 1 2 3 4
2.实现:
解决两个问题:
a)整数数组可能重复
b)可以快速求得离散化后的值
可以用C++库函数实现.用vector<int> alls;保存带离散化数值.
sort(alls.begin(),alls.end()); alls.erase(unique(alls.begin(),alls.end()),alls.end());
实际上在sort()将原数组排序.
erase() + unique() 的作用是去重,保证离散化前后值一一对应.
3.查找:
查询在原数组x离散化后的值:二分查找,x在排序+去重后的数值下标即离散化的值.
离散化前后数值的相对关系没有改变,在此基础上省去不必要的中间冗余空间.
对于计算区间和我们只需要知道相对关系即可.
时间复杂度
离散化:log(nlogn)( 排序.去重时间复杂度O(n) )
查询: 二分过程:O(logn)
C++ 代码
/*
* 下标的范围在2e9,而下标出现的次数为n(n个x)+2m(m个l和m个r)3e5
* 我们可以先将下标离散化再用前缀和求解
*/
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int Max_N = 3e5 + 10;
typedef pair<int,int> pii;
int n, m;
int a[Max_N], s[Max_N]; //存储离散化后的值 和 离散化后的前缀和
vector<int> alls; //存储待离散化的下标
vector<pii> add, query; //存储添加个查询操作
//返回原数组x离散化后的值(也就是在alls中的下标)
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; // >=x 的最左端
else l = mid + 1;
}
return l + 1; //统一加上1偏移量 方便前缀和
}
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});
alls.push_back(x);
}
for( int i = 0; i<m; i++ )
{
int l, r;
scanf("%d%d",&l,&r);
query.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( int i = 0; i<n; i++ )
{
int x = find( add[i].first );
a[x] += add[i].second;
}
//求离散化后的前缀和
for( int i = 1; i<=alls.size(); i++ )
{
s[i] = a[i] + s[i-1];
}
for( int i = 0; i<m; i++ )
{
int l = find( query[i].first ), r = find( query[i].second );
printf("%d\n",s[r]-s[l-1]);
}
return 0;
}
unique函数
有序数组当前只出现一次的数值满足:
1.第一个位置
2.与前一个元素值不同
双指针思路:
j保存对应i的最大不同数值的数目下标.在i增加时, j不减.
vector<int>::iterator unique(vector<int> &v)
{
int j = 0;
for( int i = 0; i < v.size(); i++ )
{
if( !i || v[i] != v[i-1] )
v[j++] = v[i];
}
return v.begin() + j; //返回第一个重复的位置
}