Discretization-algorithm

离散化

定义

离散化（Discretization），把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。通俗的说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。例如：
原数据：1, 999, 100000, 15；处理后：1,3,4,2。
原数据：{100, 200}，{20, 50000}，{1, 400}；处理后：{3,4}，{2,6}，{1,5}。
有的时候，我们会发现对于一个序列，它的值域很大，对应算法的复杂度是 Θ(值域) 的。离散化是程序设计中一个常用的技巧，它可以有效的降低时间复杂度。其基本思想就是在众多可能的情况中，只考虑需要用的值。离散化可以改进一个低效的算法，甚至实现根本不可能实现的算法。例如，在建造线段树空间不够的情况下，可以考虑离散化。

离散化常与差分、前缀和、树状数组、线段树结合考查。

实现原理

为了确保不出错且尽可能地提高效率，我们希望离散化能实现以下几种功能：
1、保证离散化后的数据非负且尽可能的小
2、离散化后各数据项之间的大小关系不变，原本相等的也要保持相等。
由此，找出数据项在原序列中的索引就是离散化的关键。

可以通过下面的方法以 O(n logn) 的时间复杂度完成离散化，n 为序列长度。离散化一共有两种方法，方法一重复元素离散化后的数字相同，方法二重复元素离散化后的数字不相同。

重复元素离散化后的数字相同

基本的步骤可以分为：
1、用一个辅助的数组把你要离散的所有数据存下来。
2、排序，排序是为了后面的二分。
3、去重，因为我们要保证相同的元素离散化后数字相同。(可以使用STL的unique去重，具体见博客Cpp-note4)
4、索引，再用二分把离散化后的数字放回原数组。

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:映射到1, 2, ...n（不加的话就是0~n-1）
}

注意事项有以下几点：
1、去重并不是把数组中的元素删去，而是重复的部分元素在数组末尾，去重之后数组的大小要减一。
2、二分的时候，注意二分的区间范围，一定是离散化后的区间。
3、如果需要多个数组同时离散化，那就把这些数组中的数都用数组存下来。

重复元素离散化后的数字不相同

基本的步骤可以分为：
1、用一个辅助的数组把你要离散的所有数据存下来。
2、排序。
3、枚举着放回原数组。

这种方法复杂度比上面那一种要优，但不能处理重复元素。它直接用结构体存储原本的数列的元素的位置，然后排序以后将他们再重新赋值。那么 rank[] 就是结构体 num[] 离散化后的结果。

一些小补充

为了减少代码量(不一定能提高时间、空间效率)，我们可以使用map去查询某个值是否存在(最大优势在于相比于数组的下标索引不会爆内存)

写在文末：我觉得离散化其实就是一种hash表的使用方式，只是需要保证本身索引的偏序关系。

模板题

火烧赤壁

火烧赤壁

题目背景

曹操平定北方以后，公元 208 年，率领大军南下，进攻刘表。他的人马还没有到荆州，刘表已经病死。他的儿子刘琮听到曹军声势浩大，吓破了胆，先派人求降了。

孙权任命周瑜为都督，拨给他三万水军，叫他同刘备协力抵抗曹操。

隆冬的十一月，天气突然回暖，刮起了东南风。

没想到东吴船队离开北岸大约二里距离，前面十条大船突然同时起火。火借风势，风助火威。十条火船，好比十条火龙一样，闯进曹军水寨。那里的船舰，都挤在一起，又躲不开，很快地都烧起来。一眨眼工夫，已经烧成一片火海。

曹操气急败坏的把你找来，要你钻入火海把连环线上着火的船只的长度统计出来！

题目描述

给定每个起火部分的起点和终点，请你求出燃烧位置的长度之和。

输入格式

第一行一个整数，表示起火的信息条数 $n$。
接下来 $n$ 行，每行两个整数 $a, b$，表示一个着火位置的起点和终点（注意：左闭右开）。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

3
-1 1
5 11
2 9

样例输出 #1

11

提示

数据规模与约定

对于全部的测试点，保证 $1 \leq n \leq 2 \times 10^4$，$-2{31} \leq a \leq b \lt 2^{31}$，且答案小于 $2^{31}$。

AC代码

#include <bits/stdc++.h>
using namespace std;
#define M 100007
#define N 1007
#define INF 0x3f3f3f3f
#define ll long long
#define db double
int a[M], b[M];
int n, ans;
int main() {
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
    }
    sort(a, a + n);
    sort(b, b + n);
    for (int i = 0; i < n; i++) {
        ans += b[i] - a[i];
        if (i + 1 < n) {
            if (b[i] > a[i + 1]) {
                ans -= b[i] - a[i + 1];
            }
        }
    }
    cout << ans;
    return 0;
}