【根号分治，鸽巢原理】#246. 【UER #7】套路
题目
首先，可以令 \(f[l][r]\) 为 \(s(l,r)\)，\(f[l][r]=min(|a[l]-a[r]|,min(f[l+1][r],f[l][r-1]))\)
这样做是 \(O(n^2)\) 的。
考虑当 m 很小，n 很大时会出现什么。
显然会出现许多大小相同的数（鸽巢原理）
考虑举个例子，如 \(m=2\),\(n=2\) 时，\(s\) 一定不超过 1。
即假如区间 \([l,r]\)，那么 \(s(l,r)\) 一定不超过 \(\dfrac{m}{r-l+1}\)，即按此长度分段。
我们发现可以通过根号分治使两个做法结合起来的。
主要是第二个如何搞
考虑枚举 \(r,s\)，那么需要找到 \(l\)，满足 \(s(l,r)\le s\)。
我们可以发现，对于 \(r\)，\(s(i,r)\le s(i+1,r)\)。
记 \(pos[s]\) 为对于 \(a[r]\) ，\(s(pos_s,r)\le s\)。
-
\(pos[s]=pos[s-1]\)
-
\(pos[s]=max(las[a[r]-s],las[a[r]+s])\)
假如直接这样做并默认 \([pos_s,r]\) 的 \(s\) 为当前枚举的并直接算贡献的话答案会偏大，因为实际上这段区间的 \(s\) 并不一定是你所枚举的，是小于等于所枚举的。
考虑 \(pos_s+1\) 满足 \(s(pos_s+1,r)>s\)，假如小于等于的话那么 \(pos_s\) 就是它。那么它的贡献最小是不是 \(s+1\)，那么我们在 \(pos_s+1\) 处认为贡献为 \(s+1\) 即可。
随着枚举 \(s\) 的增大，会对于每一个区间取到其本身的 \(s\)。
#include
using namespace std;
int rd() {
int f=1,sum=0; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) {sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
return sum*f;
}
void pr(int x) {
int f=1,tot=0; static int st[30];
if(x<0) x=-x,f=-1;
while(x) st[++tot]=x%10,x/=10;
if(!tot) putchar('0');
else for(int i=tot;i>=1;i--) putchar(st[i]+'0');
}
#define N (int)(2e5+5)
#define ll long long
int n,m,k,bl,a[N],f[N],g[N],las[N],pos[N];
ll ans=0;
signed main() {
n=rd(); m=rd(); k=rd(); bl=sqrt(n);
for(int i=1;i<=n;i++) a[i]=rd();
for(int r=1;r<=n;r++) {
for(int i=max(1,r-bl);i<=r;i++) g[i]=f[i],f[i]=0;
for(int l=r-1;l>=max(1,r-bl+1);l--) {
if(l==r-1) {
f[l]=abs(a[l]-a[r]);
if(r-l+1>=k) ans=max(ans,1ll*(r-l)*f[l]);
} else {
f[l]=min(abs(a[l]-a[r]),min(f[l+1],g[l]));
if(r-l+1>=k) ans=max(ans,1ll*(r-l)*f[l]);
}
}
}
for(int r=1;r<=n;r++) {
for(int i=0;i<=m/bl;i++) {
if(i) pos[i]=max(pos[i],pos[i-1]);
if(a[r]+i<=m) pos[i]=max(pos[i],las[a[r]+i]);
if(a[r]-i>=1) pos[i]=max(pos[i],las[a[r]-i]);
if(r-(pos[i]+1)+1>=max(bl,k)) ans=max(ans,1ll*(r-pos[i]-1)*(i+1));
}
las[a[r]]=r;
}
cout<