# 坐标压缩图解：保留顺序，别弄丢长度

用原坐标与压缩秩的双尺动画，看懂端点排序去重、差分事件与区间覆盖长度。压缩保留先后，不保留距离；三格可以代表2、1、5个单位。

原文 / Canonical: https://crazycloud.cc/learn/coordinate-compression
作者: crazycloudcc
首次发布: 2026-10-21
更新: 2026-10-21

本阅读版与网页共用课程数据；互动请访问原文。

## 一句话答案

坐标压缩把排序去重后的坐标X[j]映射为连续下标j，保留大小顺序与相等关系，不保留坐标差。计算半开区间的并集长度时，在起点加1、终点减1；先累加当前位置事件，再对覆盖数大于0的单元加上X[j+1]−X[j]，而不是加1。

## 适用条件与边界

本课计算数轴上有限个左闭右开区间[l,r)的连续长度，要求l≤r。空区间[a,a)长度0；负坐标合法。演示使用两个区间和预设，模型支持空集合、至多1000段、−10⁹到10⁹的整数端点，拒绝逆序、非整数、无穷与越界输入。整数只是保证计算精确，不把问题变成统计整数点。

## 不变量

应用D[j]后，active等于整个[X[j],X[j+1])的覆盖数。压缩秩只负责定位，X负责保留原长度；累计值等于已扫描正覆盖单元的真实宽度之和。

## 逐步例子

1. 从原创例子[2,5)、[4,10)开始，收集2、5、4、10，数值排序去重得到X=[2,4,5,10]，对应秩0、1、2、3。
2. 在每段左端的秩加1、右端的秩减1，得到D=[1,1,−1,−1]。同一坐标的事件要累加，不能相互覆盖。空区间的+1与−1在同点抵消。
3. 经过X[0]=2，active=1，整段[2,4)都被覆盖，长度是4−2=2。经过4再加1，active=2，[4,5)仍只计一次，贡献5−4=1。
4. 经过5减1，active=1，[5,10)贡献10−5=5。总并集长度2+1+5=8，不是压缩后的3格，也不是按重数加权的9。
5. 正确性：所有成员变化都只发生在收集的端点。单个区间对边界x的前缀贡献是1(x≥l)−1(x≥r)，恰在l≤x<r时为1；逐段相加便是右侧单元的覆盖数。
6. 相邻端点形成的半开单元不重不漏；每个正覆盖单元按原宽度计一次，所以结果恰是并集长度。最后一个端点没有右侧单元，不可访问X[m]或凭空补一格。
7. 相接[0,3)、[3,8)在3的事件抵消，没有正长度空隙；重复[2,5)两次只把覆盖数变成2，长度仍3。只有[4,4)时没有正长度单元，答案0。

## 复杂度与数值边界

n段至多2n个不同端点。排序与二分找秩的通用实现为O(n log n)时间、O(n)额外空间；本演示用Map保存秩，查找按通常的哈希表期望常数时间分析，排序仍占主导。并集完全落在最小与最大端点之间，在模型±10⁹范围内长度至多2×10⁹，可由JavaScript Number精确表示。仅检查每个端点是安全整数不足以保证它们的差安全；更大整数要用BigInt或检查过的宽整数。C++应在相减前把端点转成足够宽的整数；不要用位运算压成32位。

## 常见误区

- 把压缩下标差当真实长度：秩2与秩3只差1，但X[3]−X[2]=10−5=5。原坐标数组不能丢。
- 先算单元再应用左边界事件：左闭右开语义要求先加D[j]，然后判断[X[j],X[j+1])的覆盖数。
- 把覆盖数乘上长度来算并集：那得到按重数计算的长度。并集只判断active>0，每段计一次。
- 把所有格都加起来：分离区间之间active=0的单元不应计入。负坐标不导致负宽度，排序后相邻原坐标差仍为正。
- 混淆连续长度与离散点数：实数闭区间[2,5]长度3，而整数点有4个。离散闭区间转[l,r+1)必须先确认对象是整数点并检查r+1溢出；不能无条件加1。
- 把一段动画当作等距变换：压缩只保序，改变了画面比例。几何距离、比例和面积一般不能在秩坐标里直接照算。

## 自测

[−4,−1)与[2,6)有三个压缩单元。总覆盖长度是多少？如果重复第一段，答案改变吗？

单元宽度是3、3、4，覆盖数1、0、1，所以总长3+4=7，中间空隙不算。重复第一段后覆盖数2、0、1，但并集仍长7。

## 边界问答：长度相等，是否就完全覆盖？

1. **目标的长度和已覆盖长度相等，能否说明每个目标点都被覆盖？** 不能仅凭长度判断。原创反例：目标是实数闭区间[2,2]，没有选择任何覆盖区间。两边长度都为0，但点2仍未被覆盖。闭区间[2,2]包含一个点；本课半开区间[2,2)才是空集。即使已确认覆盖集合包含于目标集合，长度相等也可能漏掉零长度的孤立点。
2. **把整数端点压缩后，怎样避免漏掉实数点或端点？** 先区分目标是连续长度、整数点数，还是覆盖每个实数点。实数闭区间[1,2]与[3,4]没有覆盖中间的2.5，不能因为整数2与3相邻就当作无缝相接。检查全部实数点覆盖时，除了相邻端点之间的开区间，还要按原题开闭约定检查端点本身；不能直接套本课只累计正长度单元的结果，也不能无条件把右端点改成r+1。

## 从本课到真实题目：保留跨度，再处理空隙

2026年10月17日结束的ABC480 C官方讲解明确使用坐标压缩与前缀计数定位未覆盖时间段。这提供了具体的学习应用，不等于有可核实的搜索量或热度。官方讲解的单独发布日期未确认。

本课的区间并集例子是独立原创的准备实验，不是该题的完整解答。原题要求最少额外按键次数，还要结合持续时间、目标时间窗及未覆盖空隙处理，不能拿这里的长度直接当答案。

连续长度不受有限个端点是否计入的影响，但覆盖事件约定、瞬时状态和离散点计数仍必须各自定义。原题的供水瞬间规则应读原题，不能直接用本课半开区间替换而不检查。

## 延伸学习

稠密数组用每个下标作为边界；稀疏坐标先排序去重，差分照常记录开始与停止，但单元的真实宽度要由原坐标相减。

[前置：差分数组的起止事件](https://crazycloud.cc/learn/difference-array)

## 参考资料

- [AtCoder ABC480 C（2026-10-17已结束）：稀疏时间端点的实际应用](https://atcoder.jp/contests/abc480/tasks/abc480_c)
- [AtCoder官方讲解：坐标压缩与前缀计数](https://atcoder.jp/contests/abc480/editorial/27255)
- [LeetCode 4086官方题面：覆盖每个实数点与闭区间边界（非本课完整解法）](https://leetcode.com/problems/minimum-interval-selection-to-cover-target-intervals/)

[返回图解实验室](https://crazycloud.cc/learn)