离散化
有序a[] 1, 3, 100, 2000, 500000
映射为 0, 1, 2, 3, 4
1、a[]中可能存在重复元素 去重
2、如何算出a[i]离散化后的值【位置】 二分查找
算法模板
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
}
模板题
假定有一个无限长的数轴,数轴上每个坐标上的数都是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
数据范围较小时可以使用前缀和算法
数据范围很大,但是实际用到的数据量较少 → 值域跨度大,但是比较稀疏 → 离散化
将位置映射成从1开始的自然数
代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 3e5 + 10;
vector<int> a, b, c, d, q, sum(N);
int find(int x) // 二分查找原坐标位置在离散后的坐标中的位置
{
int l = 0, r = q.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (q[mid] >= x) r = mid;
else l = mid + 1;
}
return l;
}
int main()
{
int n, m, x, y, l, r;
scanf("%d%d", &n, &m);
for(int i = 0; i < n; i ++ )
{
scanf("%d%d", &x, &y);
a.push_back(x); // a用于记录原始坐标位置,用于数值的插入
q.push_back(x); // q用于计算离散化后的区间
b.push_back(y); // b用于存储待插入的数值
}
for(int i = 0; i < m; i ++ )
{
scanf("%d%d", &l, &r);
c.push_back(l); // c用于记录待查找区间和的左端坐标
q.push_back(l); // 为了查找区间和,需要把涉及到的所有坐标进行离散化
d.push_back(r); // d用于记录待查找区间和的右端坐标
q.push_back(r);
}
sort(q.begin(), q.end()); // 将所有坐标排序
q.erase(unique(q.begin(), q.end()), q.end()); // 去重
for (int i = 0; i < n; i ++ )
sum[find(a[i])] += b[i]; // 根据离散化后的位置依次插入值
for (int i = 1; i < q.size(); i ++ ) sum[i] += sum[i - 1]; // 计算前缀和
for (int i = 0; i < m; i ++ )
cout << sum[find(d[i])] - sum[find(c[i]) - 1] << endl; //计算区间和
return 0;
}
Y老师版本
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII; // 使用pair类型简化数据对的存储
const int N = 3e5 + 10; //有三种坐标
int n, m;
int a[N], s[N];
vector<int> alls;
vector<PII> add, query;
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 r + 1; //将坐标映射成1 ~ alls.size,便于前缀和的边界处理
}
// unique函数返回的是迭代器
// 【基本思想】双指针算法
/*
1 1 2 2 2 3 4 5 5 5 6
不重复的数满足的性质:
1.是第一个数
2.与前一个数不同 a[i] != a[i - 1]
*/
vector<int>::iterator unique(vector<int> &a) //函数形参为引用类型
{
int j = 0;
for (int i = 0; i < a.size(); i ++ ) // i查找数组中的不重复元素
{
if (!i || a[i] != a[i - 1])
a[j ++ ] = a[i]; // a[0] ~ a[j - 1]存储所有a中不重复元素
}
return a.begin() + j;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i ++ )
{
int x, c;
cin >> x >> c;
add.push_back({x, c});
alls.push_back(x);
}
for (int i = 0; i < m; i ++ )
{
int l, r;
cin >> 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());
// unique函数删除序列中所有相邻的重复元素(只保留一个)
// 本质是将重复的元素移动到数组的末尾
// 返回迭代器,迭代器指向的是重复元素的首地址
alls.erase(unique(alls), alls.end()); // 自己实现unique函数
// 处理插入
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;
}