回滚尺取（不删除尺取）学习笔记

这东西也叫 baka's trick。

众所周知，添加元素方便但删除元素不方便的情况下可以用回滚莫队来代替莫队，那尺取可以用什么代替呢？

回滚尺取！

具体做法

设要处理的数组长度为 $n$，且从 $1$ 开始编号，位置 $i$ 的状态为 $a_i$。

首先引入一个指针 $mid$，令它初始为 $1$。

然后令左指针 $l$ 指向 $mid$。设当前状态为 $L$，在 $l\ge 1$ 且 $L\cup a_l$ 合法的情况下不断让 $L=L\cup a_l$ 且左移 $l$。并记录下这一过程下的 $L$，记 $l$ 为 $x$ 时的 $L$ 为 $tmp_x$。

接下来令右指针 $r$ 指向 $mid+1$，设当前状态为 $R$：

1. 令 $R=R\cup a_r$

2. 在 $tmp_l\cup R$ 不合法的情况下不断右移 $l$ 指针，直到 $l>mid$ 或者 $tmp_l\cup R$ 合法

3. 若此时 $l\le mid$，那么更新答案；否则令 $mid=r$，跳出循环

4. 令 $r=r+1$，若 $l>n$，那么跳出循环；否则，返回步骤 $1$

跳出循环后注意 $l$ 大于 $n$ 的话就说明计算完了，可以结束整个尺取。

伪代码如下：

// merge(val,val2)：返回状态 val 和状态 val2 合并后的状态 
// cant(val)：若状态 val 合法，返回 true，否则返回 false
int ans=0;
for(int mid=1;mid<n;)
{
	int l,r;
	// 左移 l，记录下一路上 [l,mid] 的状态 
	int L=0;
	for(l=mid;l>=1;l--)
	{
		L=merge(L,a[l]);
		tmp[l]=L;
		if(cant(L)) 
		{
			break;
		}
	}
	l++;
	// 右移 r 
	int R=0;
	for(r=mid+1;r<=n;r++)
	{
		R=merge(R,a[r]);
		while(l<=mid&&cant(merge(tmp[l],R))) // 不断右移 l 直到状态合法或者 l 大于 mid 
		{
			l++;
		}
		if(l<=mid)
		{
			ans=max(ans,r-l+1); // 更新答案 
		}
		else
		{
			mid=r; // 开始新一轮尺取 
			break;
		}
	}
	if(r>n) // 计算完了，尺取结束 
	{
		break;
	}
}

经典例题

CF1548B Integers Have Friends

考虑 $x,y$ 对 $m$ 取余的结果相同这个东西的本质。

设 $x\mod m=y\mod m=k$，那么 $|(x-k)-(y-k)|$ 一定可以被 $m$ 整除，即 $|x-y|$ 可以被 $m$ 整除。

考虑推广到三个数，设它们为 $x,y,z$。显然只有当 $\gcd(|x-y|,|y-z|)> 1$ 时才能够找到合法的 $m$。

所以这个问题便转化为求一个最长的区间 $[l,r]$，使得 $\gcd(|a_l-a_{l+1}|,|a_{l+1}-a_{l+2}|,\cdots,|a_{m-1}-a_m|)>1$。

很明显，普通的尺取无法处理这个问题，因为添加元素很简单，但是删除元素很难。所以我们需要使用回滚尺取。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

int n;
long long a[200005],tmp[200005];

inline long long gcd(long long a,long long b)
{
	if(a==0||b==0)
	{
		return a+b;
	}
	long long t=a%b;
	while(t!=0)
	{
		a=b;
		b=t;
		t=a%b;
	}
	return b;
}

inline long long ckjabs(long long x)
{
	return x<0?-x:x;
}

int main()
{
	int _;
	scanf("%d",&_);
	while(_--)
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%lld",&a[i]);
		}
		int ans=1;
		for(int mid=1;mid<n;)
		{
			int l,r;
			long long L=0;
			for(l=mid;l>=1;l--)
			{
				L=gcd(L,ckjabs(a[mid]-a[l]));
				tmp[l]=L;
				if(L==1)
				{
					break;
				}
			}
			l++;
			long long R=0;
			for(r=mid+1;r<=n;r++)
			{
				R=gcd(R,ckjabs(a[r]-a[mid]));
				while(l<=mid&&gcd(R,tmp[l])==1)
				{
					l++;
				}
				if(l<=mid)
				{
					ans=max(ans,r-l+1);
				}
				else
				{
					mid=r;
					break;
				}
			}
			if(r>n)
			{
				break;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}