不带删的尺取

# 不带删的尺取 ## 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