大概思路是求完 $height$ 数组之后用并查集维护从大到小的合并。应该是合并策略有错或是后半部分细节有错。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+5;
#define ll long long
char a[MAXN],b[MAXN],s[MAXN];
int n,k,sa[MAXN<<1],rk[MAXN<<1],oldrk[MAXN<<1];
int h[MAXN],p[MAXN];
int fa[MAXN],suma[MAXN],sumb[MAXN];
ll ans;
int find(int x)
{
	if(!x)return 0;
	if(fa[x]==x)return x;
	return fa[x]=find(fa[x]);
}
void merge(int x,int y,int v)
{
	v=min(v,k);
	x=find(x),y=find(y);
	if(x==y)return;
	if(!x||!y)return;
	fa[x]=y;
	int sa1=suma[x],sb1=sumb[x],sa2=suma[y],sb2=sumb[y];
	if(sa1-sb1<0&&sa2-sb2>0)
	{
		ans+=v*min(-sa1+sb1,sa2-sb2);
	}
	if(sa1-sb1>0&&sa2-sb2<0)
	{
		ans+=v*min(sa1-sb1,-sa2+sb2);
	}
	suma[y]+=sa1,sumb[y]+=sb1;
}
int main()
{
	cin>>n>>k;
	scanf("%s",a+1);
	scanf("%s",b+1);
	for(int i=1;i<=2*n+1;i++)
	{
		s[i]=i>n?b[i-n-1]:a[i];
	}
	s[n+1]='&';
	n=2*n+1;
	for(int i=1;i<=n;i++)sa[i]=i,rk[i]=s[i];
	for(int w=1;w<n;w<<=1)
	{
		sort(sa+1,sa+1+n,[&](int x,int y){
		return rk[x]==rk[y]?rk[x+w]<rk[y+w]:rk[x]<rk[y];
		});
		memcpy(oldrk,rk,sizeof rk);
		for(int i=1,p=0;i<=n;i++)
		{
			if(oldrk[sa[i]]==oldrk[sa[i-1]]&&
			oldrk[sa[i]+w]==oldrk[sa[i-1]+w])rk[sa[i]]=p;
			else rk[sa[i]]=++p;
		}
	}
	n>>=1;
	for(int i=1;i<=n-k+1;i++)suma[rk[i]]++;
	for(int i=n+2;i<=2*n+2-k;i++)sumb[rk[i]]++;
	n=n*2+1;
	int c=0;
	for(int i=1;i<=n;i++)
	{
		p[i]=i;
		if(rk[i]==1)continue;
		if(c)c--;
		while(s[i+c]==s[sa[rk[i]-1]+c])c++;
		h[rk[i]]=c;
	}
	sort(p+1,p+1+n,[&](int x,int y){return h[x]>h[y];});
	for(int i=1;i<=n;i++)
	{
		fa[p[i]]=p[i];
		if(!fa[p[i]-1])
		{
			fa[p[i]-1]=p[i]-1;
			merge(p[i]-1,p[i],h[p[i]]);
			fa[p[i]-1]=0;suma[p[i]-1]=sumb[p[i]-1]=0;
		}
		merge(p[i]-1,p[i],h[p[i]]);
		merge(p[i],p[i]+1,h[p[i]]);
	}
//	for(int i=1;i<=n;i++)cout<<rk[i]<<" ";puts("");
//	for(int i=1;i<=n;i++)cout<<h[i]<<" ";puts("");
	n>>=1;
	ans=1ll*(n-k+1)*k-ans;
	cout<<ans;
	return 0;
}
/*
5 1
aaaaa
aaaaa
*/