【UOJ 246】[UER #7] 套路

相关链接

题目传送门：http://uoj.ac/contest/35/problem/246
官方题解：http://matthew99.blog.uoj.ac/blog/2085

解题报告

这题真™是套路深啊！
一言不合就根号大军了

具体来说的话，我们考虑答案的区间长度为 $ len$
并且钦定一个阀值 $ S$

1. 考虑 $ len<S$ 的情况
   我们枚举右端点，暴力向左扫 $ S$ 个就可以了

2. 考虑 $ len \ge S$ 的情况
   我们发现相似度不会超过 $ \frac{m}{{len – 1}}$
   于是考虑在权值上暴力向两边扫 $ S$ 个

这样的话，我们就可以在 $ O(nS + n\frac{m}{s})$ 的复杂度内解决这个问题了
不难发现，当 $ S = \sqrt m$ 时复杂度最优

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200000+9;

int n,m,K,S,a[N],gap[N],lst[N];
LL vout;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret * f;
}

int main() {
	n = read(); m = read(); 
	K = read(); S = sqrt(m) + 1;
	for (int i=1;i<=n;i++) a[i] = read();
	
	memset(gap,60,sizeof(gap));
	for (int i=1;i<=n;i++) {
		for (int j=i-1;j>=i-S&&j;--j) {
			gap[j] = min(gap[j], gap[j+1]);
			gap[j] = min(gap[j], abs(a[i] - a[j]));
			if (i-j+1 >= K) vout = max(vout, (LL)(i - j) * gap[j]);
		}
	}
	memset(gap,0,sizeof(gap));
	for (int i=1;i<=n;i++) {
		for (int j=0;j<=S;j++) {
			if (j) gap[j] = max(gap[j], gap[j-1]);
			if (a[i]-j >= 1) gap[j] = max(gap[j], lst[a[i]-j]);
			if (a[i]+j <= m) gap[j] = max(gap[j], lst[a[i]+j]);
			if (i-gap[j] >= K) vout = max(vout, (LL)(i-gap[j]-1) * (j+1)); 
		}
		lst[a[i]] = i;
	}
	printf("%lld\n",vout);
	return 0;
}