Description：

给一个字符串 $S$ ，求： $$ \sum_{1\leqslant i<j\leqslant n}lcp(i,j)lcs(i,j)[lcp(i,j)\leqslant k_1][lcs(i,j)\leqslant k_2] $$ $1\leqslant n\leqslant 10^5$

Solution1：

首先建出正串和反串的后缀树，然后由于 $lcp(i,j)=s[LCA(i,j)].maxl$ ，那么我们设 $val[i]=(s[i].maxl>k?0:s[i].maxl)$ ，然后问题就变成了： $$ \sum_{1\leqslant i<j\leqslant n}val_1(LCA_1(i,j))val_2(LCA_2(i,j)) $$ 于是就可以边分树合并或者边分治 $+$ 虚树统计答案了。

Code1：

没有代码

Solution2：

对于两个位置 $i,j$ ，我们考虑把 $lcs(i,j)$ 和 $lcp(i,j)$ 拼起来得到一个长为 $lcs(i,j)+lcp(i,j)-1$ ，并且再往后或者往前一个字符都不相同的串，我们可以计算出这样的一个串的贡献是： $$ \sum_{i=\max(len-k_2+1,1)}^{\min(k_1,len)}i\times (len-i+1) $$ 我们可以对于所有的 $len$ 预处理这个值，然后我们建出 $S$ 的后缀数组，考虑像品酒大会那样合并，也就是说从大到小一次去掉隔板，那么两个后缀 $(i,j)$ 会产生贡献当且仅当 $S[i-1]\ne S[j-1]$ 并且 $lcp(i,j)\ne 0$ ，那么我们可以计算所有后缀对的贡献，然后减掉相同字符的，这个开一个 $26$ 的桶记一下就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<vector>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n;

#define MAXN 200010

char s[MAXN];

int k1,k2;

int c[MAXN],c1[MAXN],c2[MAXN],sa[MAXN],h[MAXN],rnk[MAXN];

vector<int> vec[MAXN];

int pc[MAXN];

void make_SA(int n,int m)

{

	int *x = c1,*y = c2;

	int p = 0;

	for(int i = 1;i <= m;++i)c[i] = 0;

	for(int i = 1;i <= n;++i)++c[x[i] = s[i]];

	for(int i = 1;i <= m;++i)c[i] += c[i - 1];

	for(int i = n;i >= 1;--i)sa[c[x[i]]--] = i;

	for(int k = 1;k <= n;k = k << 1)

	{

		p = 0;

		for(int i = 1;i <= n;++i)y[i] = 0;

		for(int i = n - k + 1;i <= n;++i)y[++p] = i;

		for(int i = 1;i <= n;++i)if(sa[i] > k)y[++p] = sa[i] - k;

		for(int i = 1;i <= m;++i)c[i] = 0;

		for(int i = 1;i <= n;++i)++c[x[y[i]]];

		for(int i = 1;i <= m;++i)c[i] += c[i - 1];

		for(int i = n;i >= 1;--i)sa[c[x[y[i]]]--] = y[i];

		p = 1;

		swap(x,y);

		x[sa[1]] = 1;

		for(int i = 2;i <= n;++i)

		{

			x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p : ++p);

		}

		if(p >= n)break;

		m = p;

	}

	for(int i = 1;i <= n;++i)rnk[sa[i]] = i;

	int k = 0;

	for(int i = 1;i <= n;++i)

	{

		if(rnk[i] == 1)continue;

		if(k)--k;

		int j = sa[rnk[i] - 1];

		while(j + k <= n && i + k <= n && s[i + k] == s[j + k])++k;

		h[rnk[i]] = k;

	}

	for(int i = 1;i <= n;++i)vec[h[i]].push_back(i);

	for(int i = 1;i <= n;++i)pc[rnk[i]] = (i == 1 ? 0 : s[i - 1] - 'a' + 1);

	return;

}

typedef unsigned long long ull;

ull val[MAXN];

ull sum1(int n){return 1ull * n * (n + 1) / 2;}

ull sum2(int n){return 1ull * n * (n + 1) * (2 * n + 1) / 6;}

ull sum1(int l,int r){return sum1(r) - sum1(l - 1);}

ull sum2(int l,int r){return sum2(r) - sum2(l - 1);}

int cnt[MAXN][27];

int f[MAXN],siz[MAXN];

int find(int x){return (f[x] == 0 ? x : f[x] = find(f[x]));}

int main()

{

	scanf("%s",s + 1);

	n = strlen(s + 1);

	scanf("%d%d",&k1,&k2);

	if(k1 < k2)

	{

		swap(k1,k2);

		for(int i = 1,j = n;i < j;++i,--j)swap(s[i],s[j]);

	}

	make_SA(n,256);

	for(int len = 1;len <= k2;++len)val[len] = sum1(len) * (len + 1) - sum2(len);

	for(int len = k2 + 1;len <= k1;++len)val[len] = sum1(len - k2 + 1,len) * (len + 1) - sum2(len - k2 + 1,len);

	for(int len = k1 + 1;len <= min(n,k1 + k2 - 1);++len)val[len] = sum1(len - k2 + 1,k1) * (len + 1) - sum2(len - k2 + 1,k1);

	ull ans = 0;

	for(int i = 1;i <= n;++i)siz[i] = 1,cnt[i][pc[i]] = 1;

	for(int i = n;i >= 1;--i)

	{

		for(vector<int>::iterator it = vec[i].begin();it != vec[i].end();++it)

		{

			int p = find(*it - 1),q = find(*it);

			ans += val[i] * siz[p] * siz[q];

			for(int x = 1;x <= 26;++x)ans -= val[i] * cnt[p][x] * cnt[q][x];

			siz[p] += siz[q];

			for(int x = 1;x <= 26;++x)cnt[p][x] += cnt[q][x];

			f[q] = p;

		}

	}

	cout << ans << endl;

	return 0;

}