【算法•日更•第二十三期】数据结构：two-pointer（尺取法）&莫队

我不是女神ヾ 2023-06-03 02:50 10阅读 0赞

▎引入

☞『例题』

一道十分easy的题：

[**洛谷P1638**][P1638]

> 长度为n的序列，m种数 找一个最短区间，使得所有数出现一遍 n≤1e6 ,m≤2e3。

☞『分析』

这道题非常的简单，但是如果不会two-pointer的话就很费劲了，我们一定会首先想到动态规划，或者直接上暴力，时间复杂度绝对不能在这么大的数据规模下接受。

那么two-pointer是什么？

正如其名，有两个指针，**注意**：此指针非彼指针，可不是C++中的指针，所以不必担心，并不难，非常easy。

两个指针分别是头指针l和尾指针r，这样这道题的算法就很清晰了：当区间\[l,r\]中的数都出现过一次时，那么就头指针l++，同时更新答案，否则尾指针r++。

总的算法时间复杂度是O(n)，也是相当快了。

▎two-pointer（尺取法）

☞『定义』

two-pointer英文直译过来叫做双指针法，意译过来叫尺取法，（小编不了解为什么叫尺取法，觉得叫two-pointer就挺舒服的，所以下文会一直叫英文名称）。

尺取法是一种比较基础的算法,一般用来解决具有单调性的区间问题. 不过，一般满足单调性的问题二分也可以做到，所以往往two-pointer能解决的题二分也可以做到。

☞『two-pointer的用处』

two-pointer通常只起到辅助或优化的作用。

其实我们或多或少已经接触过two-pointer了，只不过你不知道它叫什么名字，所以这篇博客中的two-pointer部分只是莫队的垫脚石。

▎莫队

☞『引入』

莫队几乎就是two-pointer，只是处理的问题不太一样。废话不多说，直接先上一道题：

**洛谷P1494**

> 长度为n的序列，每个点有点权c，m次询问 每次询问一个区间内，随机取两个数相等的概率 m,n,c≤5e4

一般莫队就是处理这样的查询多次区间的问题。（有兴趣可以做一做）

☞『定义』

莫队算法主要是用于解决不带修改只有查询的一类区间问题。

☞『算法思想核心』

比方说当前有一个**大区间**（也就是数列），还有若干**查询的区间**。

![1551435-20190725112924936-642659566.png][]

假设我们已经知道一个区间\[l,r\]的答案是多少。

![1551435-20190725113100710-1166589442.png][]

那么我们就可以轻易扩展：

![1551435-20190725113247402-1966892985.png][]

我们就可以用极少的时间O(x)知道\[l,r+1\]，\[l,r-1\]，\[l-1,r\]，\[l+1,r\]的答案，以此来暴力扩展至下一个询问区间，就能知道它的答案了。

所以这是极其暴力的。

☞『为什么说它是优雅的暴力』

这个算法时间复杂度是O(n√nx)，最坏也不会到达O(n2)，因此，尽管暴力，也很优雅。

转载于:https://www.cnblogs.com/TFLS-gzr/p/11240147.html

[P1638]: https://www.luogu.org/problem/P1638
[1551435-20190725112924936-642659566.png]: /images/20230601/bacf440c16184f60937f2a4dafe8b305.png
[1551435-20190725113100710-1166589442.png]: /images/20230601/929752a5c32f43d0b799f6ba1c77fe60.png
[1551435-20190725113247402-1966892985.png]: /images/20230601/5da490bbea1f4a19972f1f78695cc622.png

发表评论取消回复

表情：

评论列表（有 0 条评论，10人围观）

还没有评论，来说两句吧...

相关阅读

相关尺取法总结

一般地，当我们要去枚举满足条件的区间权值的区间，可以用遍历双指针 l 和 r 的做法去枚举第一个满足条件的区间，然后去维护其他数据，这样的做法就是尺取法，它的复杂度为O(n)

矫情吗；*/ 2024年03月31日 15:50/ 0 赞/ 68 阅读

相关尺取法模板

题目描述博览馆正在展出由世上最佳的 M 位画家所画的图画。 wangjy想到博览馆去看这几位大师的作品。可是，那里的博览馆有一个很奇怪的规定，就是在购买门票

迈不过友情╰/ 2023年10月11日 10:42/ 0 赞/ 59 阅读

相关莫队算法

https://www.cnblogs.com/WAMonster/p/10118934.html 转载于:https://www.cnblogs.com/Aiahtwo/p

左手的ㄟ右手/ 2023年08月17日 16:26/ 0 赞/ 134 阅读

相关【算法•日更•第四十三期】QQ for linux

　　废话不多说，直接看一张图：　　![1551435-20190814185233383-371284311.png][] 　　没错，这是QQ，但是这有什么稀奇的？但是在

浅浅的花香味﹌/ 2023年06月03日 02:52/ 0 赞/ 5 阅读

相关【算法•日更•第二十三期】数据结构：two-pointer（尺取法）&莫队

▎引入 ☞『例题』　　一道十分easy的题：　　[洛谷P1638][P1638] > 长度为n的序列，m种数找一个最短区间，使得所有数出现一遍 n≤1e6 ,m≤

我不是女神ヾ/ 2023年06月03日 02:50/ 0 赞/ 11 阅读

相关【算法•日更•第二十二期】数据结构：线段树

链接在此： [【算法•日更•第二十二期】数据结构：线段树][Link 1] PS：真没想到博客园的markdown不能用。作业部落是个好东西。转载于:https:/

一时失言乱红尘/ 2023年06月03日 02:50/ 0 赞/ 8 阅读

相关【算法•日更•第二十期】构造分治

▎什么是分治？ ☞『定义』　　分治，字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简

向右看齐/ 2023年06月03日 02:50/ 0 赞/ 22 阅读

相关【算法•日更•第二十一期】数据结构：差分与前缀和

▎前言　　首先来说明一下，查分和前缀和并不像数据结构，更多的是技巧，只不过是被归类为数据结构中的东西。 ▎前缀和 ☞『什么是前缀和？』　　前缀和其实就是给定一个数列

浅浅的花香味﹌/ 2023年06月03日 02:50/ 0 赞/ 12 阅读

相关算法--尺取法

尺取法尺取法通常是指对数组保存一对下标（起点，终点），然后根据实际情况交替推进两个端点直到得出答案的方法，这种操作很像是尺取虫爬行的方式故得名。我们先来看看POJ的

￡神魔★判官ぃ/ 2022年08月21日 02:08/ 0 赞/ 186 阅读

相关【算法•日更•第四十三期】QQ for linux

　　废话不多说，直接看一张图：　　![1551435-20190814185233383-371284311.png][] 　　没错，这是QQ，但是这有什么稀奇的？但是在

柔情只为你懂/ 2021年10月26日 15:58/ 0 赞/ 231 阅读