离散化笔记

离散化的适用条件

• 离散化用于区间求和问题
• 对于数域极大，而数的量很少的情况下

离散化的意思

• 背景：对于一个极大数域上的零星几个数进行操作后，求某段区间内的和

  • 其实意思就是大数域映射到一个小数域内。比如我的操作是：第 $30$ 位加 $10$，第 $2000$ 位加 $50$,第 $10^6$ 位加 $100$，映射后我的操作就是a[1] += 10，a[2] += 50，a[3] += 100，也就是说，我们将零散的数域变得紧凑。

  • 我们如何做到将序列号变紧密而且不重复呢？

    • 首先，我们将需要转化的序列号存在一个数组a[]内，序列号就是我们在大数域内进行操作时的序列号（操作包括对某一号元素进行改值，或者是求区间之和的时候区间的左右端点。这些都是大数域上的序列号）
    • 之后，我们将这些序列号进行排序，然后去掉重复的号。
      • 这步操作的意思是，每个大数域上的序列号在小数域上只能有一个编号与其对应，所以需要去除重复的大序列号
    • 我们用数组a[]的下标作为小数域上与大数域相对应的编号
    • 所以说我们其实是通过一个数组来将序列号缩小的

  • 最后我们使用前缀和算法快速求得多个询问的区间和即可

AcWing 802. 区间和

题目链接：AcWing 802. 区间和

CODE

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> pii; 	 // 定义一个pair类型的别名PII，用于存储一对整数

int n, m; 	 // n和 m 分别表示插入操作和查询操作的数量
const int N = 300010; 	// 定义一个常量N，作为数组的大小
int a[N], s[N]; 	 	// a数组用于存储每个位置的数值，s数组用于存储前缀和

vector<int> alls; 	 		// alls向量用于存储所有出现过的数
vector<pii> add, query;		// add向量用于存储所有的插入操作，query向量用于存储所有的查询操作

int l, r;  	// l和r用于存储查询操作的左右边界
int x, c;  	// x和c用于存储插入操作的数和次数

int find(int x) 	 // find函数用于在alls向量中找到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;
}

int main()
{
    cin >> n >> m;  	// 输入插入操作和查询操作的数量
    while (n -- ){
        cin >> x >> c;
        add.push_back({x, c});
        
        alls.push_back(x); 	 // 将x加入到alls向量中
    }
    
    while (m -- ){
        cin >> l >> r;
        query.push_back({l, r});
        
        alls.push_back(l);  	// 将l和r加入到alls向量中
        alls.push_back(r);
    }
    
    // 去重
    sort(alls.begin(), alls.end());  	// 对alls向量进行排序
    alls.erase(unique(alls.begin(), alls.end()), alls.end());  // 删除alls向量中的重复元素
    
    // 找加入元素的位置并初始化加入数组
    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){
        l = find(item.first), r = find(item.second);
        printf("%d\n", s[r] - s[l - 1]);
    }
}

• 其实由上述过程和代码我们可以发现，我们用数组来缩小数域的思路与哈希表不谋而合，所以说我们可以用哈希表来存我们的操作数的序列号，这样的话能将二分的 $O(logn)$ 优化到哈希表的 $O(1)$

• 但是我们不能用手写的简易哈希表（单指开放寻址和拉链法，能优化成map当我没说）
  因为开放寻址法中，我们需要对对所有数进行取模操作，而模量N是较小的，而数据的编号很大，所以就可能出现我们映射的范围出现问题，例如一个区间[l, r]，我们用的模量N满足：$l<N<r$，这个时候我们有个尴尬的问题，我们的l映射之后比r大，那么再对这个区间求和时就回出现错误

• 这个时候就需要我们伟大的 $STL$ 出场了，unordered_map很好的解决了我们的问题
  

  
  不得不说，C++真的很牛逼啊，那老头真吊

CODE2

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int, int> pii;

int n, m;
const int N = 300010;
int a[N], s[N];
vector<int> alls;
vector<pii> add, query;
int l, r;
int x, c;

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;
}



int main()
{
    cin >> n >> m;
    while (n -- ){
        cin >> x >> c;
        add.push_back({x, c});
        
        alls.push_back(x);
    }
    
    while (m -- ){
        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());
    
    unordered_map<int, int> indx;
    for(int i = 1; i <= alls.size(); ++i) indx[alls[i - 1]] = i;
    
    // 找加入元素的位置并初始化加入数组
    for(auto item : add){
        int x = indx[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){
        l = indx[item.first], r = indx[item.second];
        printf("%d\n", s[r] - s[l - 1]);
    }
}

这个代码是我从评论区抄的，位置：https://www.acwing.com/solution/content/13511/，往下翻评论区有个哈希表代码

但是我怎么都看不懂他哈希表的赋值操作

for(int i = 1; i <= alls.size(); ++i) indx[alls[i - 1]] = i;

艹！！！！！！！！！为什么！！！！！！！！！
问bing，他跟我说因为是我在之前对alls[]数组排序去重了，所以区间[l, r]肯定不会映射出错，r映射完肯定比l大，但是我问他是因为键有序所以导致哈希表映射后相对顺序不变吗，它又说不是，然后就是一堆我看不懂的谜语，一直复读复读复读，啊啊啊啊啊啊啊好痛苦啊啊啊啊啊啊

我把对键的赋值改了，不赋为i，但是又 $WA$，真的很烦啊，想不出来为什么，等我以后深入一下 $STL$ 再说吧 <_>，蒟蒻是这样的。