不带删的尺取

1.前言

1.前置知识：尺取算法。

2.默认一个区间的结果是一个值（如区间max，区间次大值，区间gcd等等），记区间的结果为 f(S)。

3.此算法是本人在做题时yy出来的，不知道之前有没有出现过，如果没有，就叫xwp尺取好了（bushi

2.算法

2.1背景

有时在加入元素复杂度很小(本算法要求在两个区间的结果已知时，合并两个区间的复杂度也很小)，而删除元素的复杂度很大时，普通的尺取就不管用了。

而此算法可以避免删除元素的操作，使得尺取的复杂度正确。

2.2 实现

1.我们维护一个中间指针 mid（初始为1），左指针 l 和右指针 r，左指针到中间指针的结果 resl ,中间指针到右指针的结果 resr。

2.右指针初始在中间指针的位置，然后左指针不停往左走，并加入当前左指针所在的元素，并维护一个数组 a,记录 a_l=resl 。如果 l==1或者 resl 不符合题目要求，则左指针停止往左走。

3.右指针往右走，此时判断 f(a_l\bigcup resr) 是否合法，如果不合法，则左指针往右走直到合法或超越中间指针。

4.若左指针没有超越中间指针，则更新答案，回到操作3，否则始中间指针指向右指针，回到操作1（如果右指针超越数组长度，则退出循环） 。

至此，我们完成了不带删的尺取。

2.3 算法正确性及复杂度证明

正确性：算法中，我们记录了所有右端点对应合法的最远左端点，所以正确性显然。

复杂度：右指针和中间指针在一直往右走，到数组长度 n 停止，所以走的次数为 O(n)。

每次左指针从中间指针往左走，必然不会超过上一次的中间指针，因为按照算法，上一次的中间指针到这一次的中间指针一定不合法，所以左指针在每个位置处出现 O(1) 次，走的次数为 O(n) 。

每次移动指针时，都要求一次加入元素或加入区间的复杂度，所以算法总复杂度为 O(n*加入元素的复杂度)。

3.例题

原题来自：https://codeforces.com/contest/1549/problem/D

题意（转化后）：给定一个长度为 n 的序列，要求求出最长字段满足子段的 gcd>1。

这题刚好符合不带删尺取的条件，如果用题解的倍增或线段树，复杂度为 O(n \log^2 n)。

如果用不带删尺取 ，复杂度为 O(nlogn)。

理论复杂度踩了正解。

update:大佬不喜勿喷，我10月份知道了这玩意叫baka's trick,确实很经典/kk