离散化

“离散化”就是把无穷大集合中的若干个元素映射为有限集合以便于统计的方法。例如在很多情况下，问题的范围虽然定义在整数集合Z，但是只涉及其中m个有限数值，并且与数值的绝对大小无关（只把这些数值作为代表，或只与它们的相对顺序有关）。此时，我们就可以把整数集合Z中的这m个整数与1~m建立映射关系。如果有一个时间、空间复杂度与数值范围Z的大小有关的算法，在离散化后，该算法的时间、空间复杂度就降低为与m相关。

具体地说，假设问题涉及int范围内的n个整数a[1]~ a[n]，这n个整数可能有重复，去重以后共有m个整数。我们要把每个整数a[i]用一个1~m之间的整数代替，并且保持大小顺序不变，即如果a[i]小于（或等于、大于）a[j]，那么代替a[i]的整数也小于（或等于、大于）代替a[j]的整数。

很简单，我们可以把a数组排序并去掉重复的数值，得到有序数组b[1]~ b[m]，在b数组的下标i与数值b[i]之间建立映射关系。若要查询整数i(1≤i≤m)代替的数值，只需直接返回b[i]；若要查询整数a[j] (1≤j≤n)被哪个1~m之间的整数代替，只需在数组b中二分查找a[j]的位置即可。

void discrete() { // 离散化
    sort(a + 1, a + n + 1);

    for (int i = 1; i <= n; i++) // 也可用STL中的unique函数
        if (i == 1 || a[i] != a[i - 1])
            b[++m] = a[i];
}

int query(int x) { // 查询x映射为哪个1~m之间的整数
    return lower_bound(b + 1, b + m + 1, x) - b;
}

不过在java中一般的索引从0开始，所以离散化代码如下

    List<Integer> discrete(List<Integer> a) { // 离散化
        Collections.sort(a);
        List<Integer> b = new ArrayList<>();
        for (int i = 0; i <= a.size(); i++)
            if (i == 0 || !Objects.equals(a.get(i), a.get(i - 1)))
                b.add(a.get(i));
        return b;
    }

    int query(int x,List<Integer> b) { // 查询x映射为哪个0~m之间的整数
        return Collections.binarySearch(b, x);
    }

一、题目逻辑（区间染色+离散化）

P1496 火烧赤壁 区间染色问题：

1. 输入n个区间[a[i], b[i]]，将这些区间“染色”；
2. 统计被染色的总长度（重复染色的区域只算一次）；
3. 因为区间范围可能很大（比如包含负数），所以用离散化把区间端点映射到小范围的连续下标，再统计长度。

二、从0开始的Java实现（核心逻辑）

步骤：

1. 收集所有区间端点，排序+去重 → 得到离散化映射表c（下标0开始）；
2. 对每个原区间[a[i], b[i]]，通过二分查找映射到c的下标x、y；
3. 用数组f标记[x, y)区间被染色；
4. 遍历c，统计被标记区间的实际长度（c[i+1] - c[i]）。

三、完整Java代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[] a = new int[n];  // 区间左端点
        int[] b = new int[n];  // 区间右端点
        List<Integer> d = new ArrayList<>();  // 收集所有端点
        
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            b[i] = sc.nextInt();
            d.add(a[i]);
            d.add(b[i]);
        }
        
        // 1. 离散化：排序+去重（下标0开始）
        Collections.sort(d);
        List<Integer> c = new ArrayList<>();
        for (int i = 0; i < d.size(); i++) {
            if (i == 0 || !d.get(i).equals(d.get(i-1))) {
                c.add(d.get(i));
            }
        }
        int m = c.size();  // 离散化后的端点数量
        
        // 2. 标记染色区间（f[i]表示c[i]到c[i+1]的区间是否被染色）
        boolean[] f = new boolean[m - 1];  // 区间数 = 端点数 - 1
        for (int i = 0; i < n; i++) {
            // 二分查找a[i]在c中的下标x
            int x = Collections.binarySearch(c, a[i]);
            // 二分查找b[i]在c中的下标y
            int y = Collections.binarySearch(c, b[i]);
            // 标记[x, y-1]对应的区间（因为f[i]对应c[i]~c[i+1]）
            for (int j = x; j < y; j++) {
                f[j] = true;
            }
        }
        
        // 3. 统计被染色的总长度
        long ans = 0;
        for (int i = 0; i < m - 1; i++) {
            if (f[i]) {
                ans += c.get(i+1) - c.get(i);
            }
        }
        System.out.println(ans);
    }
}

四、举例解答

问题1：为什么f的长度不是m，而是m-1？

核心原因：f数组的每个元素对应“离散化后相邻两个端点之间的区间”，而非“端点本身”；m个端点只能划分出m-1个连续区间，因此f的长度是m-1。

举个直观例子：

假设离散化后的端点数组c = [1,3,4,6]（m=4个端点），这些端点把数轴分成3个区间：

• c[0]→c[1]：[1,3] → 对应f[0]
• c[1]→c[2]：[3,4] → 对应f[1]
• c[2]→c[3]：[4,6] → 对应f[2]

可见：m=4个端点 → m-1=3个区间 → f数组只需长度3，就能覆盖所有需要统计的区间。

如果把f长度设为m，会出现“无意义的元素”（比如f[3]对应c[3]→c[4]，但c[4]不存在），既浪费空间，又容易导致越界。

问题2：染色为什么是[x, y)（只染到y-1），而不是[x,y]？

核心逻辑：离散化后的区间是“左闭右开”，且f[j]对应c[j] ~ c[j+1]，要覆盖原区间[a[i], b[i]]，只需标记到y-1即可。

分两步拆解：

第一步：原区间[a[i], b[i]]的离散化映射

假设原区间是[1,4]，离散化后的端点c = [1,3,4,6]：

• a[i]=1 → 二分查找下标x=0（对应c[0]=1）
• b[i]=4 → 二分查找下标y=2（对应c[2]=4）

第二步：为什么只标记j从x到y-1？

我们要覆盖的是[1,4]，对应离散化后的区间：

• j=0 → c[0]~c[1] = [1,3]（属于[1,4]，需要染色）
• j=1 → c[1]~c[2] = [3,4]（属于[1,4]，需要染色）
• j=2 → c[2]~c[3] = [4,6]（不属于[1,4]，无需染色）

因此只需标记j=x到j=y-1（即0~1），就能完整覆盖原区间[1,4]。

如果错误标记[x,y]（0~2），会把[4,6]也染上色，导致统计结果偏大（比如原区间长度是3，错误统计成5）。

问题3：“染色”的本质是标记“区间”，而非标记“端点”

题目要求统计“被染色的总长度”，长度是区间的属性，不是端点的属性。比如端点3本身没有长度，只有[1,3]、[3,4]这类区间才有长度。

因此：

• f[j] = true → 表示c[j] ~ c[j+1]这个区间被染色；
• 遍历f数组时，只要f[j]为true，就累加c[j+1]-c[j]（该区间的实际长度）。

五、测试示例

输入（比如原题目中的[-1,1]转化为[1,2]）：

1
1 2

输出：

1

输入多个区间：

2
1 3
2 4

输出（染色区间是[1,4]，长度3）：

3