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

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

l 和 r 都只会各自遍历数组一遍，总的复杂度是 O(n*加入一个元素的复杂度)

``````#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);
}
}
``````