【根号分治，鸽巢原理】#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。

  1. pos[s]=pos[s-1]
  2. 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 <bits/stdc++.h>
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<<ans;
    return 0;
}