离散化（算法）

目录

• 一、离散化的概念
• 二、离散化的模板
• 三、离散化的应用
• • 题目
  • 思路分析
  • 代码实现

    ---

    一、离散化的概念

    离散化是一种将连续数据映射到离散值的过程。它通常用于优化某些算法，尤其是与区间查询相关的问题。

    
    （图片来源网络，侵删）

    在离散化过程中，我们将一组实数转换为一组整数，使得原始数据的顺序和区间关系得以保留。具体地说，我们将原始数据排序，然后为每个不同的值分配一个整数。这个整数是该值在排序后出现的位置，即离散化后的数值。

    假设我们有以下一组实数：{ 3.5 , 2.1 , 5.6 , 1.2 , 3.5 3.5, 2.1, 5.6, 1.2, 3.5 3.5,2.1,5.6,1.2,3.5}。对它们进行排序后，得到 { 1.2 , 2.1 , 3.5 , 3.5 , 5.6 1.2, 2.1, 3.5, 3.5, 5.6 1.2,2.1,3.5,3.5,5.6}。接着，我们可以为每个不同的值分配一个整数，例如：

    1.2 → 1 1.2 → 1 1.2→1

    2.1 → 2 2.1 → 2 2.1→2

    3.5 → 3 3.5 → 3 3.5→3

    5.6 → 4 5.6 → 4 5.6→4

    最终，我们将原始数据替换为离散化后的整数，得到 { 3 , 2 , 4 , 1 , 3 3, 2, 4, 1, 3 3,2,4,1,3} 。这些整数可以用于解决一些与区间查询相关的问题，例如线段树、树状数组等算法。

    二、离散化的模板

    vector 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
            int mid = l + r > 1;
            if(alls[mid] >= x) r = mid;
            else l = mid + 1;
        }
        return l;
    }
    

    三、离散化的应用

    题目

    假定有一个无限长的数轴，数轴上每个坐标上的数都是 0 0 0。

    现在，我们首先进行 n n n 次操作，每次操作将某一位置 x x x 上的数加 c c c。

    接下来，进行 m m m 次询问，每个询问包含两个整数 l l l 和 r r r，你需要求出在区间 [ l , r ] [l,r] [l,r] 之间的所有数的和。

    输入格式：

    第一行包含两个整数 n n n 和 m m m。

    接下来 n n n 行，每行包含两个整数 x x x 和 c c c。

    再接下来 m m m 行，每行包含两个整数 l l l 和 r r r。

    输出格式：

    共 m m m 行，每行输出一个询问中所求的区间内数字和。

    数据范围：

    − 1 0 9 ≤ x ≤ 1 0 9 −10^9≤x≤10^9 −109≤x≤109

    1 ≤ n ≤ 1 0 5 1≤n≤10^5 1≤n≤105

    1 ≤ m ≤ 1 0 5 1≤m≤10^5 1≤m≤105

    − 1 0 9 ≤ l ≤ r ≤ 1 0 9 −10^9≤l≤r≤10^9 −109≤l≤r≤109

    − 10000 ≤ c ≤ 10000 −10000≤c≤10000 −10000≤c≤10000

    输入样例：

    3 3
    1 2
    3 6
    7 5
    1 3
    4 6
    7 8
    

    输出样例：

    
    （图片来源网络，侵删）

    8
    0
    5
    

    思路分析

    由于 1 ≤ n ≤ 1 0 5 1≤n≤10^5 1≤n≤105 和 1 ≤ m ≤ 1 0 5 1≤m≤10^5 1≤m≤105 所掉用的数字范围较小，而数轴范围较大，故可以将通过离散化处理，将 − 1 0 9 -10^9 −109 ~ 1 0 9 10^9 109范围缩为 1 0 5 10^5 105左右，大大提高效率。

    

    
    

    代码实现

    tip：注意范围问题，s是从1开始的数组，所以可以通过调整二分法，将返回下标都加上1。

    #define _CRT_SECURE_NO_WARNINGS
    #include
    #include
    #include
    using namespace std;
    typedef pair PII;
    const int N = 3 * 1e5 + 10;
    int a[N], s[N];
    vector alls;
    vector add, query;
    // 二分查找
    int find(int x)
    {
    	int l = 0, r = alls.size() - 1;
    	while (l > 1);
    		if (alls[mid] >= x) r = mid;
    		else l = mid + 1;
    	}
    	return l + 1; // 由于S是从1开始的，所以对应映射位置都往前提一位
    }
    int main()
    {
    	int n, m;
    	cin >> n >> m;
    	for (int i = 0; i > x >> c;
    		add.push_back({x, c});
    		alls.push_back(x);
    	}
    	for (int i = 0; i > 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 (auto& item : add)
    	{
    		int x = find(item.first);
    		a[x] += item.second;
    	}
    	for (int i = 1; i 
    		int l = find(item.first), r = find(item.second);
    		cout