前言

前面的米娜桑把提高组,省选的算法讲了一遍又一遍,向我这种蒟蒻,该听不懂的还是听不懂. 所以我写了这篇博客来介绍一下尺取法,即使它只是一个普及组的简单算法也非常有意思.

算法描述

Codeforces中显示它的算法名称叫做"two pointers". 直译成中文的话叫双指针法. 怎么说呢……做到提高组之后,很多oier仅仅是觉得好像有这么一个两个指针从左到右扫一遍的算法存在,却不知道它的名字.(其实是因为大佬们根本没把它当个算法) 这个算法不是很难,却很有意思. 尺取法是一种比较基础的算法,一般用来解决具有单调性的区间问题. 当然,说到单调性,大家都会想到二分. 尺取法能做的题,有很大的概率也可以用二分解决,不过尺取和二分的复杂度在不同的题目中往往是不同的. 所以尺取法的题大概也是找到可二分性然后优化之. 我想不到类比尺取法的实际问题,所以我只能给了很多例题. 大家如果有的话可以告诉我,我将非常感谢. 维护两个指针 l,r ,每次确定区间的左端点,让 r 不断向右移动,直到满足条件停下,维护一下答案,直到 r>n 或者其它情况(视题目而定). 而实际中很多算法都要用到尺取法来辅助或者优化计算,尤其是分治算法.

例题

poj 3061 Sequence(http://poj.org/problem?id=3061)

给出一个序列,求区间和大于或者等于S的最短区间长度. 先想暴力.枚举每一个区间起点 l ,往右去找位置 r ,直到 [l,r] 的区间和大于或者等于 r 为止. 这时我们注意到一个性质.给出的所有数都是正整数,即它们的前缀和是单调递增的. 因此可以运用二分优化暴力. 求出数列的前缀和 sum ,枚举 l ,二分找出 sum[r]-sum[l-1] 区间和刚好大于等于 S 的最小 r . 能不能把时间复杂度再优化一下呢?答案当然是可以. 我们定义三个变量 l,r,now ,表示现在取到的区间的左右两个端点,和 [l,r] 的区间和. 每一次当 now>=s ,我们就让 r 停止向右移动. 所以当 l 不断增加的时候, r 端点不可能会往左移动,因此对于每一个 l , r 也是单调的. 证明如下:当 [l,r] 的区间和小于 S 时, [l,r-1] 就不可能大于或者等于 S ,因为 a[r] 是个正数. [l+1,r-1] 就更不可能,所以当 l 向右移动的时候, r 不可能向左移动. 代码就不难写出了.

洛谷 p1638 逛画展(https://www.luogu.org/problemnew/show/P1638)

求刚好拥有所有m种数字的最短区间. 这一次我们会发现随着 l 的增加, r 也不可能会往左移动. 也就是说如果 [l,r] 刚好有 m 种画的时候 [l,r-1] 不可能有 m 种画, [l+1,r-1] 就更不可能. 开一个 cnt 数组,存储 [l,r] 区间内 1\to m 每一种画出现了多少幅. 用 now 存储 [l,r] 区间内有多少种画. 那么我们可以这样维护.

UVA 11572 Unique Snowflakes(https://vjudge.net/problem/UVA-11572)

求没有重复数字的最长区间. 暴力的话是对于每一个位置 l 找在它右边离它最远不出现重复数字的位置 f(l) . f(l) 单调不降,所以还是开 cnt 数组维护区间 [l,r] 内每一个数出现的次数,有一个数次数大于 1 就把 l 向右推,否则一路把 r 向右开过去. 你说数据范围太大不能开数组? map 去重! 这样的话推动 [l,r] 移动的复杂度就是 O(log) 的了.

Atcoder 4142 Xor Sum 2(https://abc098.contest.atcoder.jp/tasks/arc098_b?lang=en)

求区间[l,r]的对数,使得A[l] xor A[l+1] xor ... xor A[r] = A[l] + A[l+1] + ... +A[r]. 当时我在ABC第98场的现场打这场比赛.一开始我没有头绪. 突然我在第30分钟的时候发现了性质用尺取法通过了此题. 注意到a xor b <= a + b,并且等号只有在a and b = 0的时候才能够取到. 那么 [l,r] 所有数的异或值等于所有数的和,必须要每一个二进制位上该区间所有数加起来最多只有一个 1 才行. 对于每一个 l 算出 f(l) 为从第 l 个数过去使得 [l,r] 满足上面条件最远能够延伸到的位置 r . 我去看了题解,题解中说显然 f(l) 单调不降,所以可以用尺取法做. 虽然听起来非常牵强,但是确实显然如此.我试着证明一下. 由于 [l,f(l)] 区间是符合题目条件的, [l+1,f(l)] 就更加符合条件(有几位上又少了几个 1 ),因此 f(l+1) 不可能比 f(l) 还小. 用 now 表示当前 [l,r] 区间的和. 每一次我们延伸 r 的时候,判断 now\ xor \ a[r] 和 now+a[r] 是否相等,如果相等就继续将 r 向右移动,否则停止. 对于这一个 l ,答案的个数就是 r-l ,因为 l\to r-1 中任意取一个位置 j , [l,j] 都是符合条件的.

洛谷 p1102 A-B数对(https://www.luogu.org/problemnew/show/P1102)

给出一串数以及一个数字c，要求计算出所有a-b=c的数对的个数.(不同位置的数字一样的数对算不同的数对) 又是一个二分尺取均可做的题目. 将 a-b=c 转化成 a=b+c ,枚举 b ,判断数组中有多少个 b+c . 首先把序列排序.维护两个下标 r1,r2 . 对于每一个枚举的 a[i] , r2-r1 就是等于 a[i]+c 的数字的总个数. 自己思考一下,排完序的时候所有 a[i]+c 都在一起, r1 指在这一坨 a[i]+c 最左端的位置, r2 指在最右端 +1 的位置.如果是二分的话,

用尺取可以代替二分处理这两个位置.

可以自己感性理解一下.

接下来的题目是和其它算法的结合,散发了尺取法不一般的魅力.

Codeforces 1042D Petya and Array(http://codeforces.com/problemset/problem/1042/D)

给一个序列,问有多少区间的和小于t. 昨天刚打的比赛,看起来很模板的一题,比赛前期AC量一直超过C题. 这题我已经写过博客,请大家看我的博客链接. Codeforces 1042D Petya and Array 题解 by Fuko_Ibuki(https://blog.csdn.net/qq_31908675/article/details/82756728)

Codeforces 47E Cannon(http://codeforces.com/problemset/problem/47/E)

感谢翻译. https://www.luogu.org/problemnew/show/CF47E 非常有意思的一道E题,没想到用到的算法都是普及组算法. 这一题的尺取法比起标算奇怪二分来不知道高到哪里去了. 我非常推荐大家去写一下这题. Codeforces 47E Cannon 题解 by Fuko_Ibuki(https://blog.csdn.net/qq_31908675/article/details/82261294)

Codeforces 939E Maximize!(http://codeforces.com/problemset/problem/939/E)

支持加入一个不小于之前所有数的数,询问整个集合中某个子集最大值减平均值的最大值. 我们思考一下性质.按顺序加入的数单调不降,符合尺取法的要求. 具体证明可以参考当场的题解,但我觉得里面的说明有一点点问题. 它写的内容是 f(i+1)-f(i)\leq 0 ,所以 f(i) 单调不降. 它的证明是正确的,不过结论应该是单调不升,其它没什么问题. 思考询问的内容,我们可以发现,要求的格式是最大值减平均值,显然最大的数字一定要选,而剩下的数字需要尽量小. 因此要求的集合就是最大的数字和若干个较小的数字. 稍微思考一下可以发现随着加入集合数字个数的增加,能够选的较小的数字的数量是不降的.我们可以利用这个单调性尺取较小数字的个数. 故主程序如下.

结合各例题,我们可以发现,尺取法就是在对于枚举每一个 l 的时候,另一个坐标 r 维护的答案也是单调的时候可以使用,能够均摊枚举的时间从而把时间复杂度降到 O(n) . 当你发现所求的问题存在类似的单调性的时候,不妨思考一下尺取法.只是有些时候尺取法推动 l,r 两个指针的复杂度达到了 O(n) ,这种时候便要另当别论了. 那么我就讲到这里.谢谢大家了.

 

本文发布于洛谷日报，特约作者：Fuko_Ibuki

原文地址：https://www.luogu.org/blog/Nero-Yuzurizaki/chi-qu-fa-xiao-jie