基础算法：离散化
离散化：
? ? ? ?普遍认知：有些数据本身很大， 自身无法作为数组的下标保存对应的属性。如果这时只是需要这堆数据的相对属性， 那么可以对其进行离散化处理。当数据只与它们之间的相对大小有关，而与具体是多少无关时，可以进行离散化。-----摘自百度百科
? ? ? ?个人认知：将无限或跨度极大的数据（个数相对少）根据相对大小映射到小范围的数字区间来处理，增加了空间复杂度，但大大优化了时间复杂度。简单了说：把题目中跨度极大的位置下标映射到0.1.2.3....n-1，创建数组来用小下标存储大下标代表的值，每次处理过程中，通过find函数建立大下标与小下标的关系，从而做到小范围区间处理。
来道例题：ACWing 802，区间和
题意：
假定有一个无限长的数轴，数轴上每个坐标上的数都是 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
分析：
? ? ? ?首先，根据题意和数据范围，普通的前缀和算法无法实现，数据跨度大，个数少，符合离散化条件。
? ? ? ?需要注意的是：因为要求前缀和，为了避免边界问题，本应成0.1.2...n-1,改为映射成1.2.3...n，故二分查找返回小坐标时都+1。
? ? ? ?其次，我们来思考针对这道题需要几步：
1.处理输入：第一步 输入下标x和需要加的值c，所以我们创建一个vector<pair<int ,int >> add将二者存入，我们还要把大下标映射到0.1.2.3...n-1,即继续创建一个vector<int> alls,把大下标存入，同时获得一个新的小下标（0.1.2.3....n-1），即完成映射。第二步，将输入的l,r同样存入vector<pair<int ,int >> query,同时存入alls(获得下标），此时存入的是大坐标，获得小下标。
代码实现：
cin >> n >> m;
? ? for (int i = 0; i < n; i ++ )
? ? {
? ? ? ? int x, c;
? ? ? ? cin >> x >> c; ?//add 存入 大下标位置 ? 与 ? 加多少
? ? ? ? add.push_back({x, c});
? ? ? ? alls.push_back(x); ? //alls ?存入大下标 同时 每个坐标都有了 新的下标 （即映射到0.1.2.3......n-1)
? ? }
? ? for (int i = 0; i < m; i ++ )
? ? {
? ? ? ? int l, r;
? ? ? ? cin >> l >> r;
? ? ? ? query.push_back({l, r}); ? ?//处理要求和区间两端 l,r ?存入的为大下标
? ? ? ? alls.push_back(l);
? ? ? ? alls.push_back(r);
? ? }
2.处理：
a.给alls排序去重；排序：根据大小依次赋予坐标1.2.3...n；去重目的：防止有多个大下标，每个下标对应的位置具有唯一性。
b.写find函数，建立下标连接；
? 这里使用二分的方法，传入大下标，返回小下标；
c.建立了联系就可以处理到小范围处理了，
处理加c：遍历add，将add.first传入find（）,得到属于它的小下标x，建立新数组a，使a[x]+=c;此步已经把大范围集中到小范围1.2.3....n了。
d.预处理小范围的前缀和：建立前缀和数组s，使s[i]=s[i-1]+a[i];(1<=i<=alls.size())注：alls的长度就是 映射的下标数和询问区间的两端。
代码实现：
// 排序去重
? ? sort(alls.begin(), alls.end()); ? //排序 ?为了二分查找
? ? alls.erase(unique(alls.begin(), alls.end()), alls.end()); //去重
? ? // 处理插入
? ? for (auto item : add)
? ? {
? ? ? ? int x = find(item.first); ? //通过find函数通过大下标找到对应的小下标
? ? ? ? a[x] += item.second; ?//集中到小范围处理
? ? }
? ? // 预处理前缀和
? ? for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i]; ?//alls的长度就是 映射的下标数和询问区间的两端
3.处理询问：遍历query ，将l，r的大下标传入find，找到对应的小下标，输出小范围内求出的前缀和即可。
代码实现：
// 处理询问
? ? for (auto item : query)
? ? {
? ? ? ? int l = find(item.first), r = find(item.second); ? //通过find函数 找到对应映射的小下标，在小范围求前缀和。
? ? ? ? cout << s[r] - s[l - 1] << endl;
? ? }
最后附上完整代码
完整代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 300010;
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;
? ? ? ? else l = mid + 1;
? ? }
? ? return r + 1; ?//传回r+1是因为使其映射从1开始（避免求前缀和的边界问题）
}
int main()
{
? ? cin >> n >> m;
? ? for (int i = 0; i < n; i ++ )
? ? {
? ? ? ? int x, c;
? ? ? ? cin >> x >> c; ?//add 存入 大下标位置 ? 与 ? 加多少
? ? ? ? add.push_back({x, c});
? ? ? ? alls.push_back(x); ? //alls ?存入大下标 同时 每个大下标都有了 小下标 （即映射到0.1.2.3......n-1)
? ? }
? ? for (int i = 0; i < m; i ++ )
? ? {
? ? ? ? int l, r;
? ? ? ? cin >> l >> r;
? ? ? ? query.push_back({l, r}); ? ?//处理要求和区间两端 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 (auto item : add)
? ? {
? ? ? ? int x = find(item.first); ? //通过find函数通过大下标找到对应的小下标
? ? ? ? a[x] += item.second; ?//集中到小范围处理
? ? }
? ? // 预处理前缀和
? ? for (int i = 1; i <= alls.size(); i ++ ) s[i] = s[i - 1] + a[i]; ?//alls的长度就是 映射的坐标数和询问区间的两端
? ? // 处理询问
? ? for (auto item : query)
? ? {
? ? ? ? int l = find(item.first), r = find(item.second); ? //通过find函数 找到对应映射的小下标，在小范围求前缀和。
? ? ? ? cout << s[r] - s[l - 1] << endl;
? ? }
? ? return 0;
}
到此此文结束。
注：初学为了理解和巩固随便写的，内容有错误欢迎提出，仅仅供自己参考！
代码 是acwing,y总的，自己添加的注释。（女朋友帮我排的版，漂亮不？嘿嘿）
?
|