最容易做流量的网站,vue做普通网站页面跳转,小米wordpress,wordpress 非插件七牛cdn全站加速整数离散化
适用条件
适用于有序的整数序列该序列的值域很大#xff0c;该序列的数的个数很少使用的是数的相对大小而非绝对大小
算法思路
原数组 a #xff1a;
数组下标#xff1a;0 1 2 3 4
数组元素#xff1a;1 2 2 5 109
映射数组 #xff1a;
数组下标该序列的数的个数很少使用的是数的相对大小而非绝对大小
算法思路
原数组 a
数组下标0 1 2 3 4
数组元素1 2 2 5 109
映射数组
数组下标0 1 2 3
数组元素0 1 2 3从0开始映射
1 2 3 4从1开始映射
原理
将数据从数组a中复制到b数组对b排序给b去重将b的下标作为象征将a数组每个元素使用二分查找在b中找到并用b的下标值替换a数组的元素值。
这样就完成了离散化操作
存在的问题
a 数组中可能存在重复的元素 去重如何算出 a 数组中每个元素离散化后的值 二分
其实就是找出在 a 数组中的下标是多少
模板
C
#includestudio.h
int main()
{
int a[100]{0};
int n;
scanf(%d,n);
for(int i0;in;i)
scanf(%d,a[i]);
for(int j0;jn-1;j){
for(int k0;kn-j-1;k){
if(a[k]a[k1]){
int ta[k];
a[k]a[k1];
a[k1]t;
}
}
}
int i0,j1;
int lenn;
while(ilen-1 jlen-1){
while(a[i]!a[j] jlen){
ij;
j;
}
while
} C
需去重
vectorint alls; //存储所有待离散化的值
sort(alls.begin(),alls.end()); //将数组中所有值排序
alls.erase(unique(alls.begin(),alls.end()),alls.end()); //去掉重复元素
//unique()函数将数组中所有元素去重并且返回去重之后数组的尾端点的下标erase()函数将返回的尾端点和数组末尾之间的数据去掉
int find(int x) //用二分求出x对应的离散化的值找到第一个的位置(从左往右找)
{
int l0,ralls.size()-1;
while(lr)
{
int midlr1;
if(alls[mid]x)
rmid;
else
lmid1;
}
return r1; //返回下标r1 表示从1开始映射r 表示从0开始映射
}
具体参考下面区间和例题
无需去重
一边插入一边映射类似于用二分优化插入排序。
使用插入排序方法将数轴上的位置的相对大小作为判断依据进行排序在每次接收时对数据进行同步处理从第二个接收开始先查看在该数组中是否对此位置进行过操作用二分查找进行判断如果有直接在对应位置上的数值进行增加如果没有使用插入排序中的插入操作把该数据直接插入数组中这样的话对于整个数组就不会有重复位置即在数轴上没有相同的位置因为会先进行查找如果发现对某个位置已经进行过操作时直接将其数值增加。所以在整个数组中没有一个相同的在数轴上的位置并且是按照相对大小进行排序的始终是有序的。
如何实现unique()函数
返回值
返回的是一个vectorint的迭代器
基本实现思路双指针算法
什么样的元素是不同的排好序之后1.它是第一个元素 2.a[i]!a[i-1]
代码
vectorint::iterator unique(vectorint a)
{
int j0;//存下当前存到第几个数j i
for(int i0;ia.size();i)//遍历所有的数
if(!i || a[i]!a[i-1])
a[j]a[i];//a[0]~a[j-1]就是所有a中不同的数
return a.begin()j;
}
例题区间和
假定有一个无限长的数轴数轴上每个坐标上的数都是0。
现在我们首先进行 n 次操作每次操作将某一位置x上的数加c。
接下来进行 m 次询问每个询问包含两个整数l和r你需要求出在区间[l, r]之间的所有数的和。
输入格式
第一行包含两个整数n和m。
接下来 n 行每行包含两个整数x和c。
再接下里 m 行每行包含两个整数l和r。
输出格式
共m行每行输出一个询问中所求的区间内数字和。
数据范围
−10e9≤x≤10e9,
1≤n,m≤10e5,
−10e9≤l≤r≤10e9,
−10000≤c≤10000
输入样例
3 3
1 2
3 6
7 5
1 3
4 6
7 8
输出样例
8
0
5
当数组下标比较小的时候数据范围比较小可以用前缀和来完成
当数据范围比较大的时候用离散化来完成 代码
//读入所有操作将用到的位置进行离散化
#includeiostream
#includevector
#includealgorithm
using namespace std;
typedef pairint, int PII; //PII将两个数绑定在一块一个作为first一个作为second
const int N 300010;//插入操作是十万(n)查询操作是二十万(2m)
int n, m;
int a[N], s[N]; //a是用到的数组成的数组s是前缀和数组
vectorint alls; //说明里面存储的是int类型相当于一个int类型的数组不用考虑数组长度alls存的是所有用到的下标
vectorPII add, query;//插入操作是pairint,int类型的数组add和query是名称
int find(int x) //求x的值离散化之后的结果求所用到位置(x)离散化之后的值//其实就是对于排序、去重之后的alls数组(所有用到的位置)返回x的下标(从0算起)/下标1(从1算起)
{int l 0, r alls.size() - 1; //size是返回vector中有多少个有效数据while (l r){int mid (l r) 1;if (alls[mid] x)r mid;elsel mid 1;}return r 1;//映射到从1开始的自然数
}
int main()
{cin n m;for (int i 0;i n;i){int x, c;cin x c;add.push_back({ x,c }); //向vector末尾加数据调用pair类型alls.push_back(x); //所有的点放在alls中包括数字的点和区间的点}for (int i 0;i m;i){int l, r;cin l r;query.push_back({ l, r }); //每次询问的左端点和右端点放在query中alls.push_back(l);alls.push_back(r);}//去重sort(alls.begin(), alls.end());//排序,指向数组数组首元素的指针指向数组末尾元素后一位指针第三个是一个函数指针也可以是函数对象【在类中对进行重载】仿函数类似于函数第三个参数用来制定排序规则alls.erase(unique(alls.begin(), alls.end()), alls.end());//unique()把数组中所有重复元素删去把不重复的元素放到数组的前面//返回的是新数组的一个最后位置把新数组最后一个位置到原来数组末尾的数据删除即去重//处理插入//erase()用来删除//处理插入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;
}
