不带删除的双指针

panyf · 2021-10-27 16:27:45 · 个人记录

%%%

给定一个长度为 n 的序列，定义 f(l,r) 为区间 l,r 内的数进行某种运算后的结果。钦定一些区间 [l,r] 是合法的而其他的区间是不合法的，保证对于每个 l 合法的 r 是一段区间，并且不存在两个合法区间满足 l_i<l_j 且 r_j<r_i，求所有合法区间的 f。

考虑双指针，但是双指针需要支持插入或删除一个数，而一些信息不方便删除或删除复杂度较高（\max,\gcd 等），所以需要只插入不删除的双指针。

适用条件：两个区间 [l,m] 和 [m+1,r] 的信息可以快速合并。

维护左指针 l 和右指针 r，再维护一个中间指针 m。

初始时指针都指向 1，然后进行若干次如下操作直到 r 指针移到 n：

1.将 l,m 指向 r 的位置，然后不停左移 l，直到区间 [l,m] 不合法，在此过程中用一个数组 p 记录信息，p_i 表示 f(i,m)。

2.然后每次将 r 指针向右移一次，并相应地右移 l 指针以保证区间 [l,r] 合法。f(l,r) 可以用 p_l 和 f(m+1,r) 求出。若 l>m，则返回步骤 1。

显然 m,r 只会向右移，而 l 左移不会超过上一次的 m（超过了区间 [l,r] 就不合法了），所以复杂度 O(n)。

模板题：CF1548B Integers Have Friends

用双指针找到差分数组的 \gcd>1 的极长区间即可，\gcd 就满足不方便删除，且可以快速合并的性质。

乘上 \gcd 的复杂度得到时间复杂度为 O(n\log a_i)。

#include<bits/stdc++.h>
using namespace std;
enum{N=200009};
using ll=long long;
ll a[N],p[N];
int main(){ios::sync_with_stdio(0),cin.tie(0);
    int T,n,i,l,r,m,s;
    ll w;
    for(cin>>T;T--;cout<<s+2<<'\n'){
        for(cin>>n,i=1,s=-1;i<=n;++i)cin>>a[i];
        for(i=r=1;i<n;++i)a[i]=a[i+1]-a[i];
        gg:;
        for(m=l=r,p[l+1]=w=0;l;--l)if((p[l]=gcd(p[l+1],a[l]))==1)break;//左移l
        if(r<n)for(++l;s=max(s,r-l),(++r)<n;){//右移r
            for(w=gcd(w,a[r]);l<=m&&gcd(p[l],w)==1;++l);//右移l
            if(l>m)goto gg;
        }
    }
    return 0;
}