Description：

求一个串字典序第 $i$ 小的子串和字典序第 $j$ 小的子串 $lcs$ 和 $lcp$ 的平方和。

$1\leqslant n\leqslant10^5$

Solution：

首先要知道字典序第 $i$ 小的子串是什么，思考后缀数组统计本质不同的字串的过程，显然 $l-height$ 就是新增加的子串，最重要的是这个统计还是按字典序统计的。那么我们只要求出 $height$ 的前缀和，然后在上面二分，得到这个子串开头的位置，然后在数过去就可以得到这个子串是什么了，然后求一下 $lcs$ 和 $lcp$ 直接算就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 200010

char s[MAXN];

int sa1[MAXN],rnk1[MAXN],height1[MAXN];

int sa2[MAXN],rnk2[MAXN],height2[MAXN];

int c1[MAXN],c2[MAXN];

int c[MAXN];

void make_SA(int n,int m,char s[],int sa[],int rnk[],int height[])

{

	int *x = c1,*y = c2;

	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;

	int p = 0;

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

	{

		p = 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;

		height[rnk[i]] = k;

	}

	return;

}

int f1[MAXN][17],f2[MAXN][17];

int lg[MAXN];

int lcp(int a,int b)

{

	if(a == -1 || b == -1)return 0;

	if(a == 0 || b == 0)return 0;

	if(a == b)return n - a + 1;

	a = rnk1[a];b = rnk1[b];if(a > b)swap(a,b);++a;

	int len = lg[b - a + 1];

	return min(f1[a][len],f1[b - (1 << len) + 1][len]);

}

int lcs(int a,int b)

{

	if(a == -1 || b == -1)return 0;

	if(a == 0 || b == 0)return 0;

	a = n - a + 1;b = n - b + 1;

	if(a == b)return n - a + 1;

	a = rnk2[a];b = rnk2[b];if(a > b)swap(a,b);++a;

	int len = lg[b - a + 1];

	return min(f2[a][len],f2[b - (1 << len) + 1][len]);

}

int ans = 0;

long long sumh[MAXN];

#define pii pair<int,int>

pii calc(long long i)

{

	if(i > sumh[n])return make_pair(-1,-1);

	int l = 1,r = n,mid;

	while(l < r)

	{

		mid = ((l + r) >> 1);

		if(sumh[mid] >= i)r = mid;

		else l = mid + 1;

	}

	return make_pair(sa1[l],sa1[l] + height1[l] + i - sumh[l - 1] - 1);

}

int main()

{

	scanf("%d%d",&n,&m);

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

	make_SA(n,256,s,sa1,rnk1,height1);

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

	make_SA(n,256,s,sa2,rnk2,height2);

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

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

	for(int k = 1;k <= 16;++k)

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

			f1[i][k] = min(f1[i][k - 1],f1[i + (1 << (k - 1))][k - 1]);

	for(int k = 1;k <= 16;++k)

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

			f2[i][k] = min(f2[i][k - 1],f2[i + (1 << (k - 1))][k - 1]);

	for(int i = 2;i <= n;++i)lg[i] = lg[i >> 1] + 1;

	for(int i = 1;i <= n;++i)sumh[i] = sumh[i - 1] + n - sa1[i] + 1 - height1[i];

	long long i,j;

	for(int k = 1;k <= m;++k)

	{

		scanf("%lld%lld",&i,&j);

		pii aa = calc(i),bb = calc(j);

		int l = min(aa.second - aa.first + 1,bb.second - bb.first + 1);

		if(aa.first == -1 || bb.first == -1)

		{

			puts("-1");

			continue;

		} 

		long long lcpp = min(l,lcp(aa.first,bb.first));

		long long lcss = min(l,lcs(aa.second,bb.second));

		printf("%lld\n",lcss * lcss + lcpp * lcpp);

	}

	return 0;

}