每天新涂墙面积如何用区间跳表思想跳过已覆盖部分？

简化版

每天新涂墙面积可以把每个单位位置看成点，用 next[i] 表示从 i 开始下一个可能未涂的位置。涂 [start,end) 时，不断跳到未涂点，计数后把它指向 i+1 的代表，避免以后重复扫描已涂位置。

详细版

直接逐格扫描所有区间可能重复访问大量已涂位置。优化方式类似并查集的“下一个未访问位置”：find(x) 返回不小于 x 的第一个未涂位置。涂某个位置 p 后，把它 union 到 p+1，表示下次从这里应跳到后面。

每个位置被真正涂一次，路径压缩后总体接近线性。适用于坐标范围可接受的题；如果坐标非常大，则要改成 TreeMap 区间维护。

完整版教学

一、为什么普通扫描会重复劳动

假设每天涂：

[1,100000)
[2,99999)
[3,99998)

后面的区间几乎都已经被第一天覆盖。如果仍然逐格检查，会反复扫大量已涂位置。

我们需要一种方法：遇到已涂位置时快速跳过，而不是一个个判断。

做法	重复访问已涂位置	适用性
每天逐格扫描	很多	区间短、数据小
`find` 跳指针	极少	坐标范围可开数组
TreeMap 区间维护	少	坐标巨大或稀疏

二、把区间覆盖看成“访问一次”的问题

每个单位位置第一次被涂时，贡献 1；之后再被任何区间覆盖，都不贡献新面积。因此每个位置只值得处理一次。

位置 5：
第一次涂 => 新面积 +1
第二次涂 => +0，应该快速跳过

这和“删除已访问点，下次找下一个未访问点”的模型很像。

三、next / find 表示什么

定义 parent[x] 表示从 x 开始，下一个可能未涂的位置。find(x) 返回当前未涂代表。

如果 x 未涂：find(x)=x
如果 x 已涂：find(x)=find(x+1)

记忆钩子：涂过的位置就像从数轴上删掉，find 帮你跳到下一个还没删的位置。

涂完位置 p 后，执行 parent[p] = find(p+1)。

四、区间 [start,end) 如何处理

半开区间 [start,end) 包含 start 到 end-1。处理过程：

p = find(start)
while p < end:
    新面积 +1
    parent[p] = find(p + 1)
    p = find(p)

每次循环都涂掉一个之前没涂过的位置，并把它跳到下一个未涂位置。

五、代码模板

class Solution {
    int[] parent;

    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }

    int[] amountPainted(int[][] paint) {
        int max = 0;
        for (int[] p : paint) max = Math.max(max, p[1]);
        parent = new int[max + 1];
        for (int i = 0; i <= max; i++) parent[i] = i;
        int[] ans = new int[paint.length];
        for (int d = 0; d < paint.length; d++) {
            int cur = find(paint[d][0]);
            while (cur < paint[d][1]) {
                ans[d]++;
                parent[cur] = find(cur + 1);
                cur = find(cur);
            }
        }
        return ans;
    }
}

数组要开到最大右端点，因为 find(cur+1) 可能访问到 end。

六、用例子推演

paint=[[1,4],[4,7],[2,5]]：

第 1 天涂 1,2,3 => 新面积 3
第 2 天涂 4,5,6 => 新面积 3
第 3 天 [2,5) 中 2,3,4 都已涂 => 新面积 0

第三天从 find(2) 会直接跳到 7 或至少跳过已涂链路，不会重新逐格检查 2、3、4 的旧状态。

七、常见误区与追问

误区：把 [start,end) 当成闭区间。 半开区间不包含 end。
误区：涂完位置后只 cur++。 这样后续仍会重复访问已涂位置，失去优化。
误区：数组没有开到最大右端。 find(cur+1) 需要访问哨兵位置。
追问：为什么像并查集？ 已涂点被指向下一个点，路径压缩后能快速跳过连续已涂段。
追问：坐标很大怎么办？ 用 TreeMap 维护已涂区间，不能开巨大数组。
追问：复杂度如何？ 每个单位位置最多被真正处理一次，路径压缩后接近线性。

八、加强记忆

每天新涂面积的关键是“已涂位置以后别再看”。把涂过的点指向下一个位置，find 负责跳到下一个未涂点；涂 [l,r) 时不断找、计数、删除当前点。它不是传统合并集合，而是用并查集思想在数轴上做跳指针。

简化版

详细版