注意到 \(s(l,r) \le \frac {m+1}{r-l+1}\) ,容易想到对长度分块。

区间长度小于 \(\sqrt m\) ,直接暴力 \(DP\)\(s(l,r)\) ,复杂度 \(O(n \sqrt m)\)

长度大于 \(\sqrt m\) ,则 \(s\) 小于 \(\sqrt m\) 。考虑枚举 \(s\) , 再枚举,求往左最多推多少。

注意要保证 \(s\) 能取到时才更新答案,即 \(s=j\) 时的左端点大于 \(s=j-1\) 时的左端点 。

实现时要注意数组不能开 \(O(n\sqrt n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cmath>
typedef long long LL;
using namespace std;
inline char gc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int getint(){
char ch=gc(); int res=0,ff=1;
while(!isdigit(ch)) ch=='-'?ff=-1:0, ch=gc();
while(isdigit(ch)) res=(res<<1)+(res<<3)+ch-'0', ch=gc();
return res*ff;
}
const int maxn=200005;
int n,m,K,a[maxn],B,pos[maxn],g[maxn],f[maxn];
LL ans;
inline int abs(int x){ return x<0?-x:x; }
inline int max(int x,int y){ return x>y?x:y; }
inline int min(int x,int y){ return x<y?x:y; }
inline void Update(LL x){ if(ans<x) ans=x; }
int main(){
freopen("uoj246.in","r",stdin);
freopen("uoj246.out","w",stdout);
n=getint(); m=getint(); K=getint(); B=sqrt(m); B+=2;
memset(f,63,sizeof(f));
for(int i=1;i<=n;i++) a[i]=getint();
for(int i=1;i<=B-1;i++){
for(int j=1;j<=n-i;j++){
f[j]=min(f[j],min(f[j+1],abs(a[j+i]-a[j])));
if(i+1>=K) Update((LL)f[j]*i);
}
}
for(int i=1;i<=n;i++){
int lst=0;
for(int j=0;j<=B;j++){
if(a[i]-j>=1) g[j]=max(g[j],pos[a[i]-j]);
if(a[i]+j<=m) g[j]=max(g[j],pos[a[i]+j]);
if(lst<g[j]&&i-lst>=K) Update((LL)(i-lst-1)*j);
lst=max(lst,g[j]);
}
pos[a[i]]=i;
}
printf("%lld\n",ans);
return 0;
}