一个我没写过的套路。

这个题目其实就是问你给你一个串，可以往前添加一些字符，往后添加一些字符，有多少种添加方式使得最终串不同。

我们先考虑向前添加字符，不难发现一个字符串向前添加字符可以得到的就是 parent 树子树内的本质不同的所有字符串。设这个串长为 $|S|$ ，子树内的本质不同串的个数为 $a$ ，当前点上最短串长为 $b$ ，那么添加方案数就是 $a+b-|S|$ 。

我们考虑往后添加字符的情况，往后添加一个字符就是在 SAM 的 DAG 往后走一步。所以如果我们设往后添加了 $k$ 个字符，此时往后走到了 $u$ 这个点，那么往前添加的方案数就是 $a_u+b_u - (|S|+k)$ 这个值。不难发现我们对所有它在 DAG 上的后继节点求和这个之后得到的是一个关于 $|S|$ 的一次函数。所以我们考虑维护这个一次函数，具体来说，我们先把 parent 树上的 $dp$ 做好，求出每个节点的 $a,b$ 然后令 $k_u=-1,b_u=a+b$ ，然后再在 DAG 上做第二个 $dp$ ，具体来说是 k[u] += k[v] , b[u] += k[v] + b[v] ，因为往后一步后长度增加了 $1$ 。

复杂度就是建 SAM 的复杂度。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 800006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , q;
char ch[MAXN];

struct SAM {
	int son[MAXN][26] , par[MAXN] , len[MAXN] , cnt , las;
	
	SAM() { cnt = las = 1; }
	
	void ins( char a ) {
		int x = a - 'a' , cur = ++ cnt , p = las;
		len[cur] = len[p] + 1;
		while( p && !son[p][x] ) son[p][x] = cur , p = par[p];
		if( !p ) par[cur] = 1;
		else {
			int q = son[p][x];
			if( len[q] == len[p] + 1 ) par[cur] = q;
			else {
				int ct = ++ cnt;
				len[ct] = len[p] + 1 , par[ct] = par[q];
				memcpy( son[ct] , son[q] , sizeof son[q] );
				par[cur] = par[q] = ct;
				for( ; son[p][x] == q ; p = par[p] ) son[p][x] = ct;
			}
		}
		las = cur;
	}
	
	vi G[MAXN];
	void addall( ) {
		rep( i , 2 , cnt ) G[par[i]].pb( i );
	}
	
	ll S[MAXN] , k[MAXN] , b[MAXN];
	int g[MAXN][20];
	void dfs( int u ) {
		S[u] = len[u] - len[par[u]];
		for( int v : G[u] ) {
			g[v][0] = u;
			rep( k , 1 , 18 ) if( g[g[v][k - 1]][k - 1] ) g[v][k] = g[g[v][k - 1]][k - 1]; else break;
			dfs( v );
			S[u] += S[v];
		}
		k[u] = -1 , b[u] = S[u] + len[par[u]] + 1;
	}
	
	int deg[MAXN] , A[MAXN] , cn;
	void wkr( ) {
		addall( );
		dfs( 1 );
		rep( i , 1 , cnt ) rep( k , 0 , 25 ) if( son[i][k] ) ++ deg[son[i][k]];
		queue<int> Q;
		Q.push( 1 );
		while( !Q.empty() ) {
			int u = Q.front() , v; Q.pop();
			A[++ cn] = u;
			rep( k , 0 , 25 ) if( ( v = son[u][k] ) && !( --deg[v] ) ) 
				Q.push( v );
		}
		reverse( A + 1 , A + 1 + cn );
		rep( i , 1 , cn ) {
			int u = A[i] , v;
			rep( t , 0 , 25 ) if( v = son[u][t] ) 
				k[u] += k[v] , b[u] += b[v] + k[v];
		}
	}
	int jump( int u , int l ) {
		per( k , 18 , 0 ) if( g[u][k] && l <= len[g[u][k]] ) u = g[u][k];
		return u;
	}
} S ;

int ps[MAXN];

void solve() {
	cin >> n >> q;
	scanf("%s",ch + 1);
	rep( i , 1 , n ) S.ins( ch[i] ) , ps[i] = S.las;
	S.wkr( );
	rep( i , 1 , q ) {
		int l , r;
		scanf("%d%d",&l,&r);
		int u = S.jump( ps[r] , r - l + 1 );
		printf("%lld\n",S.k[u] * ( r - l + 1 ) + S.b[u]);
	}
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}