Description
我们称一个数列为一个好的 \(k-d\) 数列，当且仅当我们在其中加上最多 \(k\) 个数之后，数列排序后为一个公差为 \(d\) 的等差数列。
你手上有一个由 \(n\) 个整数组成的数列 \(a\)。你的任务是找到它的最长连续子串，使得满足子串为好的 \(k-d\) 数列。
Solution
如果一段序列是合法的 \(k-d\) 数列，显然有两个明显的限制。
- 序列的数没有重复的。
- 序列的所有数对 \(d\) 同余。
根据条件 2，我们可以把序列分成若干段模 \(d\) 相等的区间，那么所求子串不能跨区间。然后可以将 \(a\) 数组整除 \(d\)，这样 \(d\) 就变为了 1。
这种区间问题，有一种经典的做法是枚举一个端点，另一个用数据结构等得到答案。
考虑枚举右端点 \(r\)，并且在枚举过程中记录 \(lst_i\)，表示 \(i\) 这个数上一次出现的位置，那么左端点 \(l\) 至少为 \(lst_{a_r}+1\) 和当前同余区间的左端点的最大值。
现在考虑怎么满足不能使用超过 \(k\) 个数。
如果加入不超过 \(k\) 个数就能得到等差数列，那么有 \(\max\{[l,r]\}-min\{[l,r]\}-(r-l)\le k\)，简单的变形得到 \(\max\{[l,r]\}-min\{[l,r]\}+l\le k+r\)。如果我们记式子左边为 \(f_l\)，那么接下来就只需要在 \([l,r]\)（这里的 \(l\) 是上文的左端点）找到最小的 \(l\) 满足 \(f_l\le k+r\)。这个可以用线段树来解决。
那么如何维护 \(f_x\)？注意到需要维护的式子中同时有最大值和最小值，考虑使用两个单调栈（一个递增一个递减），维护是类似的，所以不妨以递减栈为例。
我们知道，递减栈在加入一个新数时，会将原本栈里的小于这个数的数全部弹出，直到遇到大于这个数的数。在这个操作中，我们发现，单调栈里的每个数其实都对应着一个区间的最大值。因此，通过区间加减就可以维护 \(\max\)，\(\min\) 同理。
Code
#include<map>
#include<cstdio>
#include<algorithm>
#define N 200005
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;
int n,k,d,ansl=1,ansr=1,l,r,top1,top2,ans,a[N],sta1[N],sta2[N];
bool bj;
struct node {ll lz,v;}tr[N<<3];
map<ll,int> lst;
void build(int x,int l,int r)
{
if (l==r) {tr[x].v=l;return;}
int mid=(l+r)>>1;
build(x<<1,l,mid);build(x<<1|1,mid+1,r);
tr[x].v=min(tr[x<<1].v,tr[x<<1|1].v);
}
void pushdown(int x)
{
if (tr[x].lz)
{
tr[x<<1].v+=tr[x].lz;tr[x<<1].lz+=tr[x].lz;
tr[x<<1|1].v+=tr[x].lz;tr[x<<1|1].lz+=tr[x].lz;
tr[x].lz=0;
}
}
void del(int x,int l,int r,int p)
{
if (p<l||p>r) return;
pushdown(x);
if (l==p&&r==p) {tr[x].v=0;return;}
int mid=(l+r)>>1;
del(x<<1,l,mid,p);del(x<<1|1,mid+1,r,p);
tr[x].v=min(tr[x<<1].v,tr[x<<1|1].v);
}
void modify(int x,int l,int r,int p,int q,int v)
{
if (l>=p&&r<=q) {tr[x].lz+=v;tr[x].v+=v;return;}
pushdown(x);
int mid=(l+r)>>1;
if (p<=mid) modify(x<<1,l,mid,p,q,v);
if (q>mid) modify(x<<1|1,mid+1,r,p,q,v);
tr[x].v=min(tr[x<<1].v,tr[x<<1|1].v);
}
int get(int x,int l,int r,ll k)
{
if (l==r) return l;
pushdown(x);
int mid=(l+r)>>1;
if (tr[x<<1].v<=k) return get(x<<1,l,mid,k);
else return get(x<<1|1,mid+1,r,k);
}
void query(int x,int l,int r,int p,int q,int k)
{
if (l>=p&&r<=q)
{
if (tr[x].v<=k) bj=true,ans=get(x,l,r,k);
return;
}
pushdown(x);
int mid=(l+r)>>1;
if (p<=mid&&!bj) query(x<<1,l,mid,p,q,k);
if (q>mid&&!bj) query(x<<1|1,mid+1,r,p,q,k);
}
int main()
{
scanf("%d%d%d",&n,&k,&d);
for (int i=1;i<=n;++i)
scanf("%lld",&a[i]),a[i]+=inf;
if (d==0)
{
int resl=0,resr=0;
for (int i=1;i<=n;++i)
{
if (a[i]!=a[i-1])
{
if (resr-resl>ansr-ansl) ansl=resl,ansr=resr;
resl=resr=i;
}
else resr++;
}
if (resr-resl>ansr-ansl) ansl=resl,ansr=resr;
printf("%d %d\n",ansl,ansr);
return 0;
}
build(1,1,n);
for (int i=1,l=1;i<=n;++i)
{
int s=l;
if (a[i]%d!=a[i-1]%d) l=i;
else l=max(l,lst[a[i]]+1);
lst[a[i]]=i;
while (s<l) del(1,1,n,s),s++;
while (top1&&sta1[top1]>=l&&a[sta1[top1]]>=a[i])
{
modify(1,1,n,sta1[top1-1]+1,sta1[top1],a[sta1[top1]]/d);
top1--;
}
modify(1,1,n,max(sta1[top1]+1,l),i,-a[i]/d);
sta1[++top1]=i;
while (top2&&sta2[top2]>=l&&a[sta2[top2]]<=a[i])
{
modify(1,1,n,sta2[top2-1]+1,sta2[top2],-a[sta2[top2]]/d);
top2--;
}
modify(1,1,n,max(l,sta2[top2]+1),i,a[i]/d);
sta2[++top2]=i;
ans=0;bj=false;
query(1,1,n,l,i,k+i);
if (ansr-ansl<i-ans) ansl=ans,ansr=i;
}
printf("%d %d\n",ansl,ansr);
return 0;
}