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

枚举全部数对或全部连续区间常常需要平方时间。如果一次比较能排除一整批候选,就不必逐个访问它们。双指针利用有序性或窗口约束,让左右边界只向一个方向移动;本章重点说明每次移动舍弃了什么,以及为什么不会漏掉答案。
第二章已经用两个下标枚举过位置对,也用左右端点表示过连续区间。这里仍在考虑相同的候选对象,区别在于:一旦证明某些候选都不可能更好,就把它们整批排除。能否排除必须由当前比较得出,不能仅凭“用了两个下标”就断定算法正确。
本章的主要实现均为独立完整程序。阅读前需要掌握排序、区间端点和频次数组。同向双指针可以维护连续区间,但指针如何移动必须由题目的具体条件推出;固定长度区间的最值维护见第九章的单调队列。
1. 从一次比较排除一批数对
先做一个小任务:给定升序数组,判断是否存在两个不同位置,其数值之和等于 。本节练习格式为第一行 ,第二行 个数,输出 YES 或 NO;规定 ,。程序会先排序,因此输入不必已经有序。
直接枚举所有 ,需要 次比较。排序后,令 ,暂时只保留左右端点之间的元素。比较最小剩余值 与最大剩余值 :
- 若 ,则 与任意剩余元素的和都不超过 ,全部偏小。所有使用位置 的剩余候选都可以删除,让 增加。
- 若 ,则 与任意剩余元素的和都不小于 ,全部偏大。所有使用位置 的剩余候选都可以删除,让 减少。
- 若相等,已经找到两个不同位置,直接成功。
不是每次比较只排除刚刚试过的一对,而是排除所有含某一端点的候选。这正是从平方次比较降到线性次比较的原因。
用 、 手算:
| 剩余下标 | 两端和 | 排除的候选 | 下一步 |
|---|---|---|---|
| 所有含位置 的剩余数对 | |||
| 所有含位置 的剩余数对 | |||
| 所有含位置 的剩余数对 | |||
| 剩余的 | ,无解 |
当 时只剩一个位置,不能与自己配对,所以循环条件是 。全过程始终保持“尚未排除的解都在 中”。每次移动都有上述排除理由;区间不足两个位置时,全部候选已经排除,便可输出无解。
#include <bits/stdc++.h>
using namespace std;
const int N=200010;
long long a[N];
int main(){
int n;
long long k;
scanf("%d%lld",&n,&k);
for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
sort(a+1,a+n+1);
int l=1,r=n;
while(l<r){
long long s=a[l]+a[r];
if(s==k){puts("YES");return 0;}
if(s<k)++l;
else --r;
}
puts("NO");
}
数组排序耗时 。扫描每轮让区间至少缩短一位,所以只有 次移动;排序后的扫描只需常数额外空间。负数不影响这个证明,只要数组已经有序,两个端点比较的大小关系就成立。
这个程序只判断有没有解。若改为统计所有位置对,找到一对后立即返回会漏掉其他方案;第 3 节会专门处理重复值的计数。
2. 首尾双指针与最少分组
简易题面:将全部纪念品分组,每组至多两件且价格和不超过 ,求最少组数。
数据范围:,,。
直接枚举所有分组,需要尝试大量配对。先考虑最贵的纪念品:它必须被安排,而能与它同组的物品受剩余容量限制最多。把价格升序排列,令最便宜、最贵的剩余物品分别为 。
若两者价格和仍超过上限, 与其他物品也不可能同组,只能单独安排。若两者能够同组,则存在一个最优方案让它们配对:原方案中若 与 配对、 与 配对,交换为 、 后,前一组合法,后一组满足 。若其中一件原本单独成组,交换后也不会增加组数。因此可以固定这一选择,继续处理剩余物品。
把交换的特殊情况也展开。如果最便宜与最贵原本已经同组,保持原样即可;若都单独成组,合并只会减少组数;若一个单独、另一个有伙伴,重新把最便宜与最贵放在一组,把原伙伴单放,组数不增加。双方都有不同伙伴时才需要上述两组之间的交换。这样,任意最优方案都能改成采用当前选择的方案。
例如上限为 ,价格为 ,先取 ,再取 ,共两组。再看 :
| 尚未安排的价格 | 两端和 | 本轮安排 | 累计组数 |
|---|---|---|---|
| 单独 | |||
| 同组 | |||
| 不再配对 | 单独 |
每轮删去的是已经有合理安排的物品,与上一节删去不可能的数对有所不同。这里还需要交换论证保证最少组数,这也是第八章贪心方法会继续讨论的证明方式。每组至多两件是论证的条件;允许三件时,不能直接沿用。
落实到本题,每轮都处理当前最贵的一件,并增加一组;若最便宜的一件可以与它配对,就一起取走。完整程序先读入上限 ,再读件数 和各件价格,排序后开始扫描;本题单价至多为 ,两件之和至多为 ,可用 。
#include <bits/stdc++.h>
using namespace std;
const int N=30010;
int a[N];
int main(){
int n,w;
cin>>w>>n;
for(int i=1;i<=n;++i)cin>>a[i];
sort(a+1,a+n+1);
int l=1,r=n,ans=0;
while(l<=r){
if(l<r&&a[l]+a[r]<=w)++l;
--r;
++ans;
}
cout<<ans<<'\n';
}
只剩一件时也必须增加一组,因此条件使用 ;但不能把这件物品与自己配对,所以相加前另判 。排序与扫描合计为 ,扫描额外空间为 。
3. 同向双指针
3.1 快慢指针去重
现在要求把数组中的不同数值升序输出。练习的输入为第一行 、第二行 个整数,输出不同值个数和这些值;规定 ,元素在 范围内。这里明确按数值去重,所以两个位置上的相同值只保留一次。
先排序,相同值就会相邻。让读取位置 扫描全部输入,让写入位置 记录已保留的长度。对于 :
| 读取位置 | 读到的值 | 是否写入 | 保留部分 |
|---|---|---|---|
| 还没有值,写入 | |||
| 与最后保留值相同 | |||
| 不同,写到位置 | |||
| 相同,跳过 | |||
| 不同,写到位置 |
第三轮把位置 改为 ,不会影响尚未读取的位置 。写指针不会超过读指针,是可以原地压缩的原因。全局数组容量覆盖 , 初始为零。
#include <bits/stdc++.h>
using namespace std;
const int N=200010;
int a[N];
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
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];
}
printf("%d\n",m);
for(int i=1;i<=m;++i)printf("%d%c",a[i],i==m?'\n':' ');
}
扫描原序列, 指向已经保留的最后一个元素。
处理完位置 后,前 个元素恰好是原来前 个元素的不同值,且依然有序。,所以写入位置始终不超过已读位置。条件中的 先处理“还没有保留元素”,此时不应该把 当成有效值比较。
3.2 差值数对
本节使用自足练习“差值数对”。原资料中的校内题库链接需要内网访问,因此以下输入、输出和范围就是本节代码所依据的完整约定。相关公开练习见 A-B 数对,提交时应以对应站点题面为准。
简易题面:给定 个非负整数和正整数 ,统计满足 的有序位置对 的数量。相同数值出现在不同位置时分别计数。
输入第一行是 ,第二行是 个数,输出一个整数表示数对数量。数据范围:,,。
枚举两个位置需要 时间。排序后,依次固定较小值 ,需要统计较大值 出现多少次。用 指向第一个不小于目标的位置, 指向第一个大于目标的位置,则相等值占据半开区间 ,贡献为 。
随着 增大,目标 不会减小。已经小于旧目标的位置也一定小于新目标,因此两个边界都不必回退。数组已经有序时,两个边界共移动至多 次。
这里循环固定的是较小值所在的位置,最终形成的有序对却是“较大值位置在前、较小值位置在后”。排序改变了存储次序,但每个原位置仍对应一个元素,且答案只求数量,因此不需要恢复原下标。
用 、 逐轮计算:
| 较小值 | 目标值 | 目标出现范围 | 增加数对 | |
|---|---|---|---|---|
表示已经走过数组末尾,不能再读取这个位置。没有目标时,两个边界相等,贡献为零。目标变大后, 可能越过原来的 ;先让 ,再寻找新目标的结束位置,可以保持区间端点合法。
以下 为全局整数数组,容量至少为 。目标值至多为 ,可用 ;数对数量可能超过 32 位整数范围,答案使用 。
#include <bits/stdc++.h>
using namespace std;
const int N=200010;
int a[N];
int main(){
int n,C;
scanf("%d%d",&n,&C);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
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;
}
printf("%lld\n",ans);
}
表中两个值为 的位置都要分别贡献答案。重复值不能去重,否则会丢失位置对;目标不存在时,两条边界相等,本轮贡献为 。
排序需要 时间,扫描需要 时间。 保证目标严格大于当前值,不会把同一位置与自身配对。
如果将范围改为允许 ,必须先问清位置对的含义。一个值出现 次时:允许 的有序对有 个;要求 的有序对有 个;无序的不同位置对只有 个。例如三个相同值分别产生 个答案。上面的代码直接用于 会得到第一种结果。若任务要求第二种结果,可在每轮贡献中减一;若要求第三种,应按相等值分段统计,不能同时计算两个方向。本节主任务的 条件正好避开了这些口径差异。
3.3 维护最短覆盖区间
例题:逛画展。
简易题面:寻找包含全部 位画家作品的最短连续区间;并列时输出左端点最小的一组。
数据范围:,,,保证有解。
枚举左右端点,再逐幅检查画家是否齐全,会反复统计同一段作品。固定右端点时,可以复用上一个窗口的频次;左端只要还有同一画家的其他作品,就能删去一幅而不失去覆盖。
窗口是闭区间 。 表示画家 的作品在窗口中有几幅, 表示频次非零的画家数。右边加入一幅时,只有它的频次从零变成一, 才增加;从一变成二并没有增加新画家。
使用 、,把每次加入和收缩写出来:
| 新右端 | 加入后及收缩动作 | 最终窗口 | 频次 | 是否更新答案 |
|---|---|---|---|---|
| 加入 | 尚不完整 | |||
| 加入 ,删去旧的 | 尚不完整 | |||
| 加入 | 尚不完整 | |||
| 加入 ,左端只剩一个 | 长度 ,记录 | |||
| 加入 ,左端仍不可删 | 长度 ,不更新 | |||
| 加入 ,依次删去左侧 | 同长,保留更早左端 |

查看最后一轮静态图。图中绿色框是闭区间窗口,灰色框是暂不在窗口内的作品。
这里的收缩只删除频次大于一的左端,因此不会让某类画家从有变成无, 无须在收缩时减少。如果采用“完整就先记录,再强行删除一个左端”的另一种写法,则频次降到零时必须减少 ;两种维护方式不能混用。
全局整数数组 分别保存作者和窗口频次,容量为 、,初始均为零。 表示还没找到完整窗口, 保存已找到的端点。原题保证有解,程序也约定无完整覆盖时输出 -1,便于将这个方法用于未保证有解的输入。
#include <bits/stdc++.h>
using namespace std;
const int N=1000010,M=2010;
int a[N],cnt[M];
int main(){
int n,m,x=0,y=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%d",&a[i]);
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;
}
}
if(ans==n+1)puts("-1");
else printf("%d %d\n",x,y);
}
例如作者序列 ,读到第四幅时,最左的一幅可以删除,得到 ;再删就缺少画家 。收缩结束后,左端对应的画家只剩一幅,继续右移就会缺失该画家。因此一旦窗口完整,它就是当前右端点对应的最短完整窗口。若某个最优窗口右端为 ,程序处理到这个 时得到的窗口不会更长,所以枚举全部右端点必然能找到全局最短答案。左右端点只向右移动,严格变短时才更新也能保留并列时更早的左端点。时间为 ,存图画与频次需要 空间。
这里的条件必须落实为频次判断: 表示已经覆盖全部画家, 表示删除最左作品仍保留该画家的其他作品。每次删除都不改变已出现的画家集合。若某个起点曾被删除,以后即使右端继续右移,也总能用保留下来的更晚起点得到同样完整且更短的区间,所以左端不需要回退。
这种维护连续区间的同向双指针也称为滑动窗口。名称本身并不能确定收缩条件:本题依据“同一画家还有其他作品”删除左端;换成其他约束,必须重新证明删除后仍满足什么条件、为什么不会漏掉答案。
4. 区间合并
本节与下一节使用自足练习“区间覆盖长度”,完整约定如下。原资料中的内网题面无法作为离线资料的前提。
简易题面:给定数轴上的 个半开区间 ,其中 。
请计算这些区间的并集长度。被多个区间覆盖的部分只能计算一次。输入第一行 ,接下来 行各给出 ,输出一个整数表示长度。
长度按数轴上的距离计算。例如 长度为 ,不是把整数 都数进去得到 。半开区间包含左端,不包含右端;单个端点本身没有长度,但端点是否属于区间会影响后面的重叠数问题。
数据范围:,。
先按左端点升序排列,维护尚未结算的最后一个合并区间 。新区间左端不超过 时,两段重叠或相接,可以合并;否则旧区间已经结束。由于后续区间左端只会更大,旧区间不会再与它们相接,可以把长度计入答案。
用按左端点排好序的 手算:
| 新读入区间 | 与待结算区间的关系 | 新的待结算区间 | 已结算长度 |
|---|---|---|---|
| 初始化 | |||
| 完全包含在原段内 | |||
| 在端点相接 | |||
| 中间有空隙 | |||
| 输入结束 | 结算最后一段 | 无 |
第二行说明右端必须取最大值,不能直接改成新右端 ,否则已经覆盖的 会丢失。遇到空隙时才把旧段永久计入答案,因为排序保证以后不会再读到能填回旧空隙的区间。
以下全局数组 保存区间,容量为 ,每项的 字段使用 ,比较函数 按左端点升序排列。题目保证至少有一个区间。
#include <bits/stdc++.h>
using namespace std;
const int N=200010;
struct Node{
long long l,r;
}a[N];
bool cmp(Node x,Node y){
return x.l<y.l;
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i)scanf("%lld%lld",&a[i].l,&a[i].r);
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;
printf("%lld\n",ans);
}
循环结束后仍有最后一段未结算,必须再累加一次。对半开区间求并集长度时, 与 可以合为 ,长度仍是 ;这不表示两段存在重叠。排序需要 时间,扫描需要 时间,扫描额外空间为 。
5. 扫描线
仍以区间覆盖长度为例。区间合并维护并集的端点;扫描线则按坐标顺序维护当前覆盖次数,也能进一步统计重叠情况。
5.1 为什么只在端点处理事件
若坐标只有几百,可以用第四章的差分记录每个位置的覆盖次数。但这里坐标可能为负,跨度可达 ,按每个整数坐标开数组已经不合适。真正能改变覆盖次数的位置只有区间端点;端点之间无论相隔一米还是十亿米,状态都不变。于是可以只保存这些变化位置,并保留它们之间的真实距离。
5.2 把端点变成事件
每个半开区间 产生两个事件:在 处覆盖次数增加 ,在 处减少 。把全部事件按坐标排序。相邻事件坐标之间没有区间开始或结束,覆盖次数保持不变,因此只需处理端点,不必逐个枚举坐标。
设当前事件坐标为 ,上一个事件坐标为 ,处理当前事件前的覆盖次数为 。它对应的是 :若 ,答案增加 ;然后统一处理坐标 上的所有增减,得到右侧下一段的覆盖次数。
例如区间 、、:
| 当前坐标 | 此前一段 | 此前覆盖次数 | 增加的长度 | 处理同坐标事件后的覆盖次数 |
|---|---|---|---|---|
| 无 | ||||
总覆盖长度为 。坐标 上同时发生一次结束和一次开始,统一处理后的覆盖次数仍为 。
处理坐标 之前, 对应的是左边的 ;处理完坐标 的两个事件后,新的 对应右边的 。两次数值恰好相同,但对应的区间不同。把状态对应哪一段说清楚,才能确定代码里的更新顺序。
5.3 先结算长度,再更新状态
以下 是全局事件数组,容量至少为 ,每项包含坐标 和变化量 。已为每个区间存入 、,事件数 。坐标、距离和答案使用 ,覆盖次数使用 。比较函数 按事件坐标升序排列。
#include <bits/stdc++.h>
using namespace std;
const int N=400010;
struct Node{
long long x;
int v;
}e[N];
bool cmp(Node a,Node b){
return a.x<b.x;
}
int main(){
int n,m=0;
scanf("%d",&n);
for(int i=1;i<=n;++i){
long long l,r;
scanf("%lld%lld",&l,&r);
e[++m]={l,1};
e[++m]={r,-1};
}
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;
}
printf("%lld\n",ans);
}
必须先按旧覆盖次数结算 ,再更新坐标 处的事件。若先更新,会把右侧区间的状态错误地用于左侧长度。相同坐标统一处理,也能避免把事件处理到一半的临时计数当成真实重叠数。求最大重叠数时,应在同坐标事件全部处理完后记录覆盖次数。
对于本题的非空半开区间,求最大重叠次数时也应在同坐标事件全部处理完后取最大值。例如 和 从未同时覆盖一个点,最大重叠为 。如果在坐标 先处理开始事件并立即取最大值,会得到临时值 ,这个值不对应任何真实位置。
若改成实数闭区间 和 ,它们在端点 的确同时存在,最大重叠应为 。此时不能直接使用半开区间的合并事件规则:可以先加入当前坐标开始的区间,记录该点覆盖数,再移除在该点结束的区间。并集长度不受单点影响,但最大重叠数受影响,必须区分两个统计目标。
端点规则由区间含义决定。连续半开区间在 处结束;整数闭区间 的差分才在 处撤销。这里直接排序原坐标即可处理大坐标,不要求先离散化;即使使用离散化,长度仍须用原坐标之差计算。
共 个事件,排序需要 时间,每个事件只处理一次,扫描需要 时间,事件数组占用 空间。
留言
可以匿名留言,无需注册或登录。昵称和邮箱均可不填,邮箱不会公开显示。
正在加载留言区…