ABS窗口约束问题#

在处理涉及绝对值约束的问题时，一类经典的形式是要求集合内的元素满足 $|a_i - a_j| \leq M$ 。这个条件表面上是复杂的 全对约束 ，即要求任意两个元素之间都必须满足特定的差值关系，然而基于绝对值的几何特性，该条件可以等价地转化为对整体 极值 的考察：

这一等价转化显著提升了算法处理的效率，它意味着我们不再需要逐一扫描 $O(N^2)$ 级别的元素对关系，而只需关注集合的边界，使得原本复杂的组合筛选问题得到了本质上的优化。

从几何视角审视，这种差值约束可以被抽象为 区间覆盖模型 。如果将每个元素 $a_i$ 看作以其为中心、半径为 $M/2$ 的闭区间 $[a_i - M/2, \, a_i + M/2]$ ，那么原问题就等价于判定这些区间是否存在 公共交集 。这一视角将数值间的距离限制转化为坐标轴上的几何覆盖，即寻找一个原点 $x$ ，使得所有选定的元素到 $x$ 的距离都不超过 $M/2$ 。

从几何视角切换至极值视角也同样成立。例如假设每个元素 $a_i$ 可以在 $[a_i - k, \, a_i + k]$ 内任意调整，我们需要判断是否存在某种方案使得最终所有元素达成一致，此时问题的本质是判断这些调整区间的交集是否非空。等价地，只需要对整体 极值 进行考察：

在一些实际应用中，我们需要从序列中选取部分元素并保证其极差不超过 $M$ 。在已知某个元素 $L$ 必须被选中的前提下，我们可以围绕 $L$ 来分析可行解的范围。显然，所有可能与 $L$ 共存的元素必须落在 $[L - M, \, L + M]$ 这一范围内。但这仅仅是必要条件，即便所有候选元素都落在此区间，最终选出的集合的极差也有可能超过 $M$ 。

为了完整解决这个问题，可以采用 枚举合法窗口 的思路：既然满足条件的集合必然落在某个长度为 $M$ 的区间内，我们可以枚举所有包含 $L$ 且总长度为 $M$ 的区间。这种方式将全局约束具象化为动态的区间筛选过程，从而方便地进行动态维护或在线处理。