简述

　　后缀数组。 　　网上什么鬼二分，不用二分，你就直接枚举所有长度为 K 的区间，查一下所有这种区间的最小值取个max输出就行了。

代码

//后缀数组 #include <cstdio> #include <algorithm> #include <cmath> #define maxn 20010 using namespace std; int N, sa[maxn], rank[maxn], height[maxn], ws[maxn], wa[maxn], wb[maxn], K, r[maxn], tmp[maxn], st[maxn][17]; bool cmp(int *r, int a, int b, int l){return r[a]==r[b] and r[a+l]==r[b+l];} void build_sa(int n, int m) { int i, j, k=0, p, *x=wa, *y=wb; for(i=0;i<m;i++)ws[i]=0; for(i=0;i<n;i++)ws[x[i]=r[i]]++; for(i=1;i<m;i++)ws[i]+=ws[i-1]; for(i=n-1;i>=0;i--)sa[--ws[x[i]]]=i; for(p=j=1;p<n;j<<=1,m=p) { for(p=0,i=n-j;i<n;i++)y[p++]=i; for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j; for(i=0;i<m;i++)ws[i]=0; for(i=0;i<n;i++)ws[x[y[i]]]++; for(i=1;i<m;i++)ws[i]+=ws[i-1]; for(i=n-1;i>=0;i--)sa[--ws[x[y[i]]]]=y[i]; for(i=1,p=1,swap(x,y),x[sa[0]]=0;i<n;i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; } for(i=0;i<n;i++)rank[sa[i]]=i; for(i=0;i<n-1;height[rank[i++]]=k) for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++); } void init() { int i, k; scanf("%d%d",&N,&K); for(i=0;i<N;i++)scanf("%d",r+i), tmp[i]=r[i]; sort(tmp+1,tmp+N); for(i=0;i<N;i++)r[i]=lower_bound(tmp+1,tmp+N+1,r[i])-tmp; build_sa(N+1,N+1); for(i=0;i<=N;i++)st[i][0]=height[i]; for(k=1;k<=15;k++)for(i=0;i+(1<<k)-1<=N;i++) st[i][k]=min(st[i][k-1],st[i+(1<<k-1)][k-1]); } int qmin(int l, int r) { int k=log2(r-l+1); return min(st[l][k],st[r-(1<<k)+1][k]); } int main() { int i, ans=0; init(); for(i=1;i+K-2<=N;i++)ans=max(ans,qmin(i,i+K-2)); printf("%d",ans); return 0; }