第五章：双指针与区间扫描

枚举全部数对或全部连续区间常常需要平方时间。如果一次比较能排除一整批候选，就不必逐个访问它们。双指针利用有序性或窗口约束，让左右边界只向一个方向移动；本章重点说明每次移动舍弃了什么，以及为什么不会漏掉答案。

阅读前需要掌握排序、区间端点和频次数组。同向双指针可以维护连续区间，但指针如何移动必须由题目的具体条件推出；固定长度区间的最值维护见第九章介绍的单调队列。

1. 首尾双指针

例题：NOIP 2007 普及组·纪念品分组。

简易题面：将全部纪念品分组，每组至多两件且价格和不超过 $w$，求最少组数。

数据范围：$1\le n\le3\times10^4$，$80\le w\le200$，$5\le p_i\le w$。

直接枚举所有分组，需要尝试大量配对。先考虑最贵的纪念品：它必须被安排，而能与它同组的物品受剩余容量限制最多。把价格升序排列，令最便宜、最贵的剩余物品分别为 $l,r$。

若两者价格和仍超过上限，$r$ 与其他物品也不可能同组，只能单独安排。若两者能够同组，则存在一个最优方案让它们配对：原方案中若 $r$ 与 $x$ 配对、$l$ 与 $y$ 配对，交换为 $(l,r)$、$(x,y)$ 后，前一组合法，后一组满足 $p_x+p_y\le p_x+p_r\le w$。若其中一件原本单独成组，交换后也不会增加组数。因此可以固定这一选择，继续处理剩余物品。

例如上限为 $100$，价格为 $20,30,70,80$，先取 $20,80$，再取 $30,70$，共两组。这个论证依赖每组至多两件；允许三件时，不能直接沿用。

落实到本题，每轮都处理当前最贵的一件，并增加一组；若最便宜的一件可以与它配对，就一起取走。以下 $a$ 已升序排列，$w$ 为单组上限；本题单价至多为 $200$，两件之和至多为 $400$，可用 $\texttt{int}$。

int l = 1, r = n, ans = 0;
while (l <= r)
{
    if (l < r && a[l] + a[r] <= w)
    {
        ++l;
    }
    --r;
    ++ans;
}

只剩一件时也必须增加一组，因此条件使用 $l\le r$；但不能把这件物品与自己配对，所以相加前另判 $l<r$。排序与扫描合计为 $O(n\log n)$，扫描额外空间为 $O(1)$。

2. 同向双指针

2.1 快慢指针去重

需要升序保留每个不同值时，先排序，再让读取位置 $i$ 扫描全部输入，让写入位置 $m$ 记录已保留的长度。全局数组 $a$ 容量覆盖 $n+1$，以下 $m$ 初始为零。

sort(a + 1, a + n + 1);
int m = 0;
for (int i = 1; i <= n; ++i)
{
    if (m == 0 || a[i] != a[m])
    {
        a[++m] = a[i];
    }
}

$i$ 扫描原序列，$m$ 指向已经保留的最后一个元素。

处理完位置 $i$ 后，前 $m$ 个元素恰好是原来前 $i$ 个元素的不同值，且依然有序。$m\le i$，所以写入位置始终不超过已读位置。条件中的 $m=0$ 先处理“还没有保留元素”，此时不应该把 $a[0]$ 当成有效值比较。

2.2 差值数对

例题：差值数对。

简易题面：给定 $n$ 个非负整数和正整数 $C$，统计满足 $a_i-a_j=C$ 的有序位置对 $(i,j)$ 的数量。相同数值出现在不同位置时分别计数。

数据范围：$1\le n\le2\times10^5$，$1\le C\le10^9$，$0\le a_i\le10^9$。

枚举两个位置需要 $O(n^2)$ 时间。排序后，依次固定较小值 $a_i$，需要统计较大值 $a_i+C$ 出现多少次。用 $l$ 指向第一个不小于目标的位置，$r$ 指向第一个大于目标的位置，则相等值占据半开区间 $[l,r)$，贡献为 $r-l$。

随着 $i$ 增大，目标 $a_i+C$ 不会减小。已经小于旧目标的位置也一定小于新目标，因此两个边界都不必回退。数组已经有序时，两个边界共移动至多 $2n$ 次。

以下 $a$ 为全局整数数组，容量至少为 $200010$。目标值至多为 $2\times10^9$，可用 $\texttt{int}$；数对数量可能超过 32 位整数范围，答案使用 $\texttt{long long}$。

sort(a + 1, a + n + 1);
int l = 1, r = 1;
long long ans = 0;
for (int i = 1; i <= n; ++i)
{
    int x = a[i] + C;
    while (l <= n && a[l] < x)
    {
        ++l;
    }
    r = max(r, l);
    while (r <= n && a[r] == x)
    {
        ++r;
    }
    ans += r - l;
}

例如序列 $1,1,2,2,3$，$C=1$。两个值为 $1$ 的位置各找到两个值为 $2$ 的位置，贡献 $4$；两个值为 $2$ 的位置各找到一个值为 $3$ 的位置，贡献 $2$，总答案为 $6$。重复值不能去重，否则会丢失位置对。

排序需要 $O(n\log n)$ 时间，扫描需要 $O(n)$ 时间。$C>0$ 保证目标严格大于当前值，不会把同一位置与自身配对。

2.3 维护最短覆盖区间

例题：逛画展。

简易题面：寻找包含全部 $m$ 位画家作品的最短连续区间；并列时输出左端点最小的一组。

数据范围：$1\le m\le2000$，$m\le n\le10^6$，$1\le a_i\le m$，保证有解。

枚举左右端点，再逐幅检查画家是否齐全，会反复统计同一段作品。固定右端点时，可以复用上一个窗口的频次；左端只要还有同一画家的其他作品，就能删去一幅而不失去覆盖。

全局整数数组 $a,cnt$ 分别保存作者和窗口频次，容量分别为 $1000010$、$2010$，$cnt$ 初始为零。$kind$ 表示当前种类数；频次从零变为一时才增加它。以下 $ans$ 初始为 $n+1$，$x,y$ 保存答案端点。

int l = 1, kind = 0, ans = n + 1;
for (int r = 1; r <= n; ++r)
{
    if (++cnt[a[r]] == 1)
    {
        ++kind;
    }
    while (cnt[a[l]] > 1)
    {
        --cnt[a[l]];
        ++l;
    }
    if (kind == m && r - l + 1 < ans)
    {
        ans = r - l + 1;
        x = l;
        y = r;
    }
}

例如作者序列 $1,1,2,3$，读到第四幅时，最左的一幅可以删除，得到 $[2,4]$；再删就缺少画家 $1$。每次都保留当前右端点对应的最短完整窗口，枚举全部右端点便覆盖了最优答案。左右端点只向右移动，严格变短时才更新也能保留并列时更早的左端点。时间为 $O(n+m)$，存图画与频次需要 $O(n+m)$ 空间。

这里的条件必须落实为频次判断：$kind=m$ 表示已经覆盖全部画家，$cnt[a[l]]>1$ 表示删除最左作品仍保留该画家的其他作品。每次删除都不改变已出现的画家集合。若某个起点曾被删除，以后即使右端继续右移，也总能用保留下来的更晚起点得到同样完整且更短的区间，所以左端不需要回退。

这种维护连续区间的同向双指针也称为滑动窗口。名称本身并不能确定收缩条件：本题依据“同一画家还有其他作品”删除左端；换成其他约束，必须重新证明删除后仍满足什么条件、为什么不会漏掉答案。

3. 区间合并

例题：区间覆盖长度。

简易题面：给定数轴上的 $n$ 个半开区间 $[l_i,r_i)$，其中 $l_i<r_i$。

请计算这些区间的并集长度。被多个区间覆盖的部分只能计算一次。

数据范围：$1\le n\le2\times10^5$，$-10^9\le l_i<r_i\le10^9$。

先按左端点升序排列，维护尚未结算的最后一个合并区间 $[l,r)$。新区间左端不超过 $r$ 时，两段重叠或相接，可以合并；否则旧区间已经结束。由于后续区间左端只会更大，旧区间不会再与它们相接，可以把长度计入答案。

以下全局数组 $a$ 保存区间，容量至少为 $200010$，每项的 $l,r$ 字段使用 $\texttt{long long}$，比较函数 $cmp$ 按左端点升序排列。题目保证至少有一个区间。

sort(a + 1, a + n + 1, cmp);
long long l = a[1].l, r = a[1].r, ans = 0;
for (int i = 2; i <= n; ++i)
{
    if (a[i].l <= r)
    {
        r = max(r, a[i].r);
    }
    else
    {
        ans += r - l;
        l = a[i].l;
        r = a[i].r;
    }
}
ans += r - l;

循环结束后仍有最后一段未结算，必须再累加一次。对半开区间求并集长度时，$[1,4)$ 与 $[4,7)$ 可以合为 $[1,7)$，长度仍是 $6$；这不表示两段存在重叠。排序需要 $O(n\log n)$ 时间，扫描需要 $O(n)$ 时间，扫描额外空间为 $O(1)$。

4. 扫描线

仍以“区间覆盖长度”为例。区间合并维护并集的端点；扫描线则按坐标顺序维护当前覆盖次数，也能进一步统计重叠情况。

4.1 把端点变成事件

每个半开区间 $[l_i,r_i)$ 产生两个事件：在 $l_i$ 处覆盖次数增加 $1$，在 $r_i$ 处减少 $1$。把全部事件按坐标排序。相邻事件坐标之间没有区间开始或结束，覆盖次数保持不变，因此只需处理端点，不必逐个枚举坐标。

设当前事件坐标为 $x$，上一个事件坐标为 $pre$，处理当前事件前的覆盖次数为 $cnt$。它对应的是 $[pre,x)$：若 $cnt>0$，答案增加 $x-pre$；然后统一处理坐标 $x$ 上的所有增减，得到右侧下一段的覆盖次数。

例如区间 $[1,4)$、$[2,5)$、$[5,7)$：

当前坐标	此前一段	此前覆盖次数	增加的长度	处理同坐标事件后的覆盖次数
$1$	无	$0$	$0$	$1$
$2$	$[1,2)$	$1$	$1$	$2$
$4$	$[2,4)$	$2$	$2$	$1$
$5$	$[4,5)$	$1$	$1$	$1$
$7$	$[5,7)$	$1$	$2$	$0$

总覆盖长度为 $6$。坐标 $5$ 上同时发生一次结束和一次开始，统一处理后的覆盖次数仍为 $1$。

4.2 先结算长度，再更新状态

以下 $e$ 是全局事件数组，容量至少为 $400010$，每项包含坐标 $x$ 和变化量 $v$。已为每个区间存入 $(l_i,1)$、$(r_i,-1)$，事件数 $m=2n$。坐标、距离和答案使用 $\texttt{long long}$，覆盖次数使用 $\texttt{int}$。比较函数 $cmp$ 按事件坐标升序排列。

sort(e + 1, e + m + 1, cmp);
long long ans = 0, pre = e[1].x;
int cnt = 0, i = 1;
while (i <= m)
{
    long long x = e[i].x;
    if (cnt > 0)
    {
        ans += x - pre;
    }
    while (i <= m && e[i].x == x)
    {
        cnt += e[i].v;
        ++i;
    }
    pre = x;
}

必须先按旧覆盖次数结算 $[pre,x)$，再更新坐标 $x$ 处的事件。若先更新，会把右侧区间的状态错误地用于左侧长度。相同坐标统一处理，也能避免把事件处理到一半的临时计数当成真实重叠数。求最大重叠数时，应在同坐标事件全部处理完后记录覆盖次数。

端点规则由区间含义决定。连续半开区间在 $r$ 处结束；整数闭区间 $[l,r]$ 的差分才在 $r+1$ 处撤销。这里直接排序原坐标即可处理大坐标，不要求先离散化；即使使用离散化，长度仍须用原坐标之差计算。

共 $2n$ 个事件，排序需要 $O(n\log n)$ 时间，每个事件只处理一次，扫描需要 $O(n)$ 时间，事件数组占用 $O(n)$ 空间。

5. 作业

巩固练习

• NOIP 2007 普及组·纪念品分组
• A-B 数对

提高训练

• 逛画展