我的算法书 - 点对问题

一句话算法

点对问题的核心是：固定一个端点，把另一个端点能提供的信息快速查出来。

问题模型

点对问题通常要求统计或优化满足条件的二元组：

(i,j),\quad i<j

例如：

逆序对： $i<j$ 且 $a_i>a_j$ 。
Two Sum： $i<j$ 且 $a_i+a_j=K$ 。
差值对： $i<j$ 且 $|a_i-a_j|\le D$ 。
树上点对：两点之间距离、颜色或权值满足条件。

最直接的做法是枚举所有点对：

cpp

        1
2
3

        for (int i = 1; i <= n; ++i)
  for (int j = i + 1; j <= n; ++j)
    check(i, j);

复杂度是 $O(n^2)$ 。当 $n$ 很大时，必须利用条件结构优化。

核心直觉

每个点对都有唯一的右端点 j。

所以可以把答案写成：

f(n)=\sum_{j=1}^{n}s(j)

其中 $s(j)$ 表示“以 $j$ 为右端点的合法左端点数量”。

这样问题就变成：

枚举 j 时，怎样快速知道左边有多少个 i 能和它配对？

如果 $s(j)$ 能 $O(1)$ 求，总复杂度是 $O(n)$ 。

如果 $s(j)$ 能 $O(\log n)$ 求，总复杂度是 $O(n\log n)$ 。

算法步骤

处理序列点对时，常用框架是：

初始化一个维护历史信息的数据结构 state。
从左到右枚举右端点 j。
用 state 计算当前贡献 $s(j)$ 。
将 $s(j)$ 加入答案。
把当前元素 a[j] 插入 state。

关键是第 3 步：不同题目需要不同的 state。

条件类型	常用数据结构	典型复杂度
相同/不同类别	桶、计数数组	$O(n)$
和或差等于目标值	哈希表、平衡树	$O(n)$ 或 $O(n\log n)$
排名、大小关系	树状数组、线段树	$O(n\log n)$
距离限制	滑动窗口	$O(n)$
窗口最值	单调队列	$O(n)$
树上距离	点分治、树形 DP	依模型而定

算法证明

关键不变量：处理右端点 j 前，state 中只保存满足 i < j 的历史点信息。

初始时 state 为空，合法。
枚举到 j 时，先查询 state，得到的点都在 j 左侧。
查询后再插入 j，所以 j 不会和自己配对。
任意合法点对 (i,j) 只会在右端点 j 被枚举时统计一次。

因此按右端点分解答案是不重不漏的。

复杂度分析

若查询 $s(j)$ 的复杂度为 $T$ ，维护 state 的单次复杂度也是 $T$ ，则总复杂度通常是：

O(nT)

常见情况：

桶或哈希表：期望 $O(n)$ 。
树状数组/线段树： $O(n\log n)$ 。
单调队列： $O(n)$ 。
点分治：常见为 $O(n\log n)$ 。

代码实现

本文是点对问题的模式识别入口，不重复放代码模板。序列配对的正式模板见本书配对问题章节：

enumeration_permutaion_combination/pair_number/index.md

树状数组统计逆序对可以参考：

data_structure/BIT/index.md

测试用例

Two Sum 点对

输入：

6 10
1 5 3 4 9 7

满足 $a_i+a_j=10$ 的点对有：

(1, 9)
(3, 7)

答案是：

二值属性不同点对

输入：

6
0 1 1 0 0 1

每个 0 可以和左侧所有 1 配对，每个 1 可以和左侧所有 0 配对，答案是：

应用分类详解

点对问题的本质是“两个对象之间满足关系”。识别时先看点对来自哪里：序列、集合、坐标平面，还是树/图。

一、序列上的历史配对

典型模式： 只要求 $i<j$ ，条件由 $a_i,a_j$ 决定。

识别信号： “前面有多少个”“两数之和”“差为 K”“颜色不同的对数”。

核心建模： 固定右端点 j，维护左侧历史信息。

应用场景	经典题目	核心思路
Two Sum 计数	配对问题章节	哈希表查 `K-a[j]`
逆序对	luogu-P1908	离散化 + 树状数组统计左侧更大数
选择客栈	luogu-P1311	按颜色维护历史可用端点

二、排序后的差值配对

典型模式： 条件和数值差、距离、大小范围有关。

识别信号： $|a_i-a_j|\le D$ 、差值不超过、最近距离。

核心建模： 先排序，再用双指针或二分确定每个端点能配对的范围。

应用场景	经典题目	核心思路
差值不超过 D 的对数	基础双指针	排序后维护合法窗口
A-B=C 数对	luogu-P1102	排序后二分或哈希计数

三、窗口限制点对

典型模式： 点对还要求下标距离不超过 k。

识别信号： “距离不超过 k”“最近 k 个”“区间内配对”。

核心建模： 枚举右端点，只维护 [j-k,j-1] 的历史信息，过期点移除。

四、树上点对

典型模式： 点对来自树，条件与路径距离、颜色、权值有关。

识别信号： “树上任意两点”“路径长度不超过 K”“颜色对数”。

核心建模： 如果条件跨子树，需要考虑 LCA、树形 DP 或点分治。点分治常用来统计经过当前重心的跨子树点对。

应用场景	经典题目	核心思路
树上距离不超过 K 的点对	POJ 1741 Tree	点分治统计跨子树路径
树形 DP 复杂度证明	本书树形 DP 章节	每对点只在某个合并处贡献一次

经典例题

1. 逆序对

固定右端点 j，需要知道左侧有多少个数大于 a[j]。把值离散化后，用树状数组查询排名区间。

2. A-B=C 数对

固定一个端点，另一个端点需要等于 a[j]+C 或 a[j]-C。可以用哈希表统计次数，也可以排序后二分。

3. 选择客栈

这是“属性配对 + 区间有效性”的组合模型。先找到哪些历史位置已经变成可用，再按颜色统计可配对数量。

4. 树上距离点对

当点对关系发生在树上路径中时，普通线性扫描不够。若要统计大量路径距离限制，常用点分治把跨子树点对集中到重心处处理。

参考

本书配对问题章节：enumeration_permutaion_combination/pair_number/index.md
本书树状数组章节：data_structure/BIT/index.md
本书双指针章节：base/two-pointer/index.md