单调队列

#include<bits/stdc++.h>
using namespace std;
int n,k,m,s[40010],sa[40010],rk[40010],cnt[40010],id[40010],oldrk[40010],h[40010],q[40010],head,tail,ans,l[40010];
int read()
{
	int r=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') w=ch=='-'?-1:w,ch=getchar();
	while(ch>='0'&&ch<='9') r=r*10+ch-'0',ch=getchar();
	return r*w;
}
int main()
{
	n=read(),k=read()-1,m=2e4;
	for(int i=1;i<=n;i++)
	s[i]=l[i]=read();
	sort(l,l+n+1);
	int len=unique(l,l+n+1)-l;
	for(int i=1;i<=n;i++)
	cnt[rk[i]=s[i]=lower_bound(l,l+len,s[i])-l]++;
	for(int i=1;i<=m;i++)
	cnt[i]+=cnt[i-1];
	for(int i=n;i;i--)
	sa[cnt[rk[i]]--]=i;
	for(int k=1;k<n;k*=2)
	{
		memset(cnt,0,sizeof(cnt));
		for(int i=1;i<=n;i++)
		id[i]=sa[i];
		for(int i=1;i<=n;i++)
		cnt[rk[id[i]+k]]++;
		for(int i=1;i<=m;i++)
		cnt[i]+=cnt[i-1];
		for(int i=n;i;i--)
		sa[cnt[rk[id[i]+k]]--]=id[i];
		memset(cnt,0,sizeof(cnt));
		for(int i=1;i<=n;i++)
		id[i]=sa[i];
		for(int i=1;i<=n;i++)
		cnt[rk[id[i]]]++;
		for(int i=1;i<=m;i++)
		cnt[i]+=cnt[i-1];
		for(int i=n;i;i--)
		sa[cnt[rk[id[i]]]--]=id[i];
		memcpy(oldrk,rk,sizeof(oldrk));
		for(int i=1,j=0;i<=n;i++)
		if(oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i]+k]==oldrk[sa[i-1]+k])
		rk[sa[i]]=j;
		else
		rk[sa[i]]=++j;
	}
	for(int i=1,j=0;i<=n;i++)
	{
		if(j)
		j--;
		while(s[i+j]==s[sa[rk[i]-1]+j])
		j++;
		h[rk[i]]=j;
	}
	head=1;
	for(int i=2;i<=n;i++)
	{
		while(head<=tail&&q[head]+k>=i)
		head++;
		while(head<=tail&&h[q[tail]]>=h[i])
		tail--;
		q[++tail]=i;
		if(i>=k&&head<=tail)
		ans=max(ans,h[q[head]]);
	}
	cout<<ans;
}