【笔记】baka’s trick(无需删除的双指针)([note] Baka’s trick (double pointer without deletion))

从这看的
对于一些求满足某一性质的最长区间的问题,可以考虑 O(n) 的双指针(或者多带个 log:ST表预处理然后枚举右端点对左端点二分,或者线段树)
常规的双指针要求向当前维护的集合中加入一个元素、删除一个元素时,都能较快地更新集合的某种函数值或性质(当然,根本上要求集合随着元素的加入,这种“函数值或性质”满足单调性,如减小、联通性)
这个算法可以做到无需删除,前提是维护的得是函数值(或者要求能够以某种形式存下述的东西?)

设左、右、中间端点 l, r, mid,当前满足条件的区间为 [l, r],数组 resl[l] 存储 [l, mid] 的函数值,resr 存储 (mid, r] 的函数值
当前 r++,接着若 [l, r] 不满足“某条件”则 l++,同时直接调用 resl[l],其与 resr 之并即为 [l, r] 的更新值
直到 [l, r] 满足“某条件”;或者 l > mid,此时令 mid = r, l = r+1,然后不断令 l– 并更新 resl,直到 [l, mid] 不再满足“某条件”(有可能一开始就不满足条件,此时区间为 [r+1, r],区间长即为 0)
l 和 r 都只会各自遍历数组一遍,总的复杂度是 O(n*加入一个元素的复杂度)

求区间最长的 gcd>1 的段(常规做法就是ST表或线段树,另外注意转化!涉及同余可以考虑移到等号一边,考虑差分数组!)
题目

#include <cstdio>
using namespace std;
typedef long long ll;
const int MAXN = 200005;
int T, N;
ll A[MAXN], resl[MAXN], resr;
ll ab(ll x) { return x < 0 ? -x : x; }
ll gcd(ll x, ll y) { return y ? gcd(y, x%y) : x; }
int max(int x, int y) { return x > y ? x : y; }
int main()
{
	for (scanf("%d", &T); T; T--) {
		scanf("%d", &N);
		for (int i=1; i<=N; i++) scanf("%lld", &A[i]);
		if (N==1) { puts("1"); continue; }
		for (int i=2; i<=N; i++) A[i-1] -= A[i], A[i-1] = ab(A[i-1]);
		//for (int i=1; i< N; i++) printf("%lld ", A[i]); puts("");
		int l = 1, r = 1, mid = 1, ans = A[1] > 1; // [l, mid], (mid, r];
		resl[1] = A[1]; if (A[1]==1) l = mid+1;
		while (r< N-1) {
			++r, resr = r==mid+1 ? A[r] : gcd(resr, A[r]);
			while (l<=mid && gcd(resl[l], resr)==1) l++;
			if (l> mid) {
				mid = r, l = r+1, resl[l] = A[l-1];
				while (l> 1 && (resl[l-1]=gcd(resl[l], A[l-1]))> 1) l--;
			}
			ans = max(ans, r-l+1);
			//printf("[%d, %d]\n", l, r);
		}
		printf("%d\n", ans+1);
	}
}
————————

From here
For some problems of finding the longest interval satisfying a certain property, we can consider the double pointer of O (n) (or preprocess with multiple log: St tables, and then enumerate the bisection of the right endpoint to the left endpoint, or the segment tree)
The conventional double pointer requires that when adding an element to the currently maintained set or deleting an element, it can quickly update some < strong > function value or property of the set < / strong > (of course, it is basically required that the “function value or property” of the set satisfies monotonicity with the addition of elements, such as reduction and connectivity)
This algorithm does not need to be deleted, provided that the < strong > function value < / strong > (or the following things can be stored in some form?)

Let the left, right and middle endpoints L, R and mid, and the interval that currently meets the conditions is [l, R]. The array resl [l] stores the function value of [l, mid], and RESR stores the function value of (mid, R)
Current R + +, then if [l, R] does not meet “a certain condition”, then l + +, and directly call resl [l], and the sum of resl and RESR is the updated value of [l, R]
Until [l, R] satisfies “certain condition”; Or L & gt; Mid, let mid = R, l = R + 1, then keep L — and update resl until [l, mid] no longer meets “certain condition” (it may not meet the condition at the beginning, at this time, the interval is [R + 1, R], and the interval length is 0)
L and R will only traverse the array once respectively, and the total complexity is O (n * the complexity of adding an element)

Find the GCD & gt; 1 (the conventional method is st table or segment tree. In addition, pay attention to transformation! If congruence is involved, you can consider moving to the equal sign side and considering the difference array!)
subject

#include <cstdio>
using namespace std;
typedef long long ll;
const int MAXN = 200005;
int T, N;
ll A[MAXN], resl[MAXN], resr;
ll ab(ll x) { return x < 0 ? -x : x; }
ll gcd(ll x, ll y) { return y ? gcd(y, x%y) : x; }
int max(int x, int y) { return x > y ? x : y; }
int main()
{
	for (scanf("%d", &T); T; T--) {
		scanf("%d", &N);
		for (int i=1; i<=N; i++) scanf("%lld", &A[i]);
		if (N==1) { puts("1"); continue; }
		for (int i=2; i<=N; i++) A[i-1] -= A[i], A[i-1] = ab(A[i-1]);
		//for (int i=1; i< N; i++) printf("%lld ", A[i]); puts("");
		int l = 1, r = 1, mid = 1, ans = A[1] > 1; // [l, mid], (mid, r];
		resl[1] = A[1]; if (A[1]==1) l = mid+1;
		while (r< N-1) {
			++r, resr = r==mid+1 ? A[r] : gcd(resr, A[r]);
			while (l<=mid && gcd(resl[l], resr)==1) l++;
			if (l> mid) {
				mid = r, l = r+1, resl[l] = A[l-1];
				while (l> 1 && (resl[l-1]=gcd(resl[l], A[l-1]))> 1) l--;
			}
			ans = max(ans, r-l+1);
			//printf("[%d, %d]\n", l, r);
		}
		printf("%d\n", ans+1);
	}
}