后缀自动机挺好毒瘤的题。
我们考虑哪些切点是不合法的。肯定是所有的匹配串都被切了。
我们考虑第一个切口的位置。
当第一个切口在第一个出现位置前时，第二个切口必须切掉所有的串。
当第一个切口在$l_{i}$和$l_{i+1}$间的时候(此时必须保证切掉第一个串)，第二个切口必须切掉$s_{i+1}$到$s_{cnt}$这些串
当第一个切口在$l_{cnt}$后时(此时依旧需要保证切掉第一个串)，第二个切口随便放。
于是我们将询问离线，对于每个询问通过在parent树上倍增来找到所对应的节点。
对于后缀自动机上每个节点，通过平衡树启发式合并来维护他的right集合，之后我们只需要维护$\sum{(l_{i+1}-l_{i}) \cdot (r_{i+1}-l_{cnt})}$即可，然后拆开式子，就是$\sum{(r_{i+1}-r_{i}) \cdot r_{i+1}}$和$\sum{r_{i+1}-r_{i}}$。
因为每个询问的长度不同，又因为我们在上述第二三种情况都需要保证切掉第一个串，所以我们所需要提取的区间也不同，这个我们直接在平衡树上乱搞一下就可以了。
之后我们就可以愉快的AC掉这道好毒瘤题啦！
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#define N 100500
#define LL long long
using namespace std; int n,m;
char s[N];
struct data{
int l,r;
LL ans;
}d[];
vector <int> V[N<<]; #define siz(_) ((!(_))?(0):((_)->size))
#define tp pair<Treap *,Treap *>
struct Treap{
Treap *ch[];
int key,size,val,maxn,minn,val2,sum2;
LL val1,sum1;
//sum1=(r[i+1]-r[i])*r[i+1];
//sum2=(r[i+1]-r[i]);
Treap(int x){
val=maxn=minn=x;
key=rand();size=;
sum1=val1=sum2=val2=;
ch[]=ch[]=NULL;
}
void pushup(){
size=siz(ch[])+siz(ch[])+;
minn=maxn=val;
sum1=val1;sum2=val2;
if(ch[]){
minn=ch[]->minn;
sum1+=ch[]->sum1;
sum2+=ch[]->sum2;
}
if(ch[]){
maxn=ch[]->maxn;
sum1+=ch[]->sum1;
sum2+=ch[]->sum2;
}
}
}*root[N<<]; Treap *merge(Treap *a,Treap *b){
if(!a)return b;
if(!b)return a;
if(a->key<=b->key){
a->ch[]=merge(a->ch[],b);
a->pushup();return a;
}
else{
b->ch[]=merge(a,b->ch[]);
b->pushup();return b;
}
}
tp split(Treap *a,int k){
if(!a)return tp(NULL,NULL);
tp x;
if(siz(a->ch[])>=k){
x=split(a->ch[],k);
a->ch[]=x.second;
a->pushup();x.second=a;
}
else{
x=split(a->ch[],k-siz(a->ch[])-);
a->ch[]=x.first;
a->pushup();x.first=a;
}
return x;
}
int getrank(Treap *rt,int x){
int k=;
while(){
if(!rt)return k;
if(rt->val<x)k+=siz(rt->ch[])+,rt=rt->ch[];
else rt=rt->ch[];
}
}
void insert(Treap *&rt,int x){
int k=getrank(rt,x);
tp t=split(rt,k);
Treap *now=new Treap(x);
if(t.first){
tp w=split(t.first,k-);
now->val1=now->sum1=1ll*(x-w.second->val)*x;
now->val2=now->sum2=(x-w.second->val);
t.first=merge(w.first,w.second);
}
if(t.second){
tp w=split(t.second,);
w.first->val1=w.first->sum1=1ll*(w.first->val-x)*w.first->val;
w.first->val2=w.first->sum2=(w.first->val-x);
t.second=merge(w.first,w.second);
}
rt=merge(merge(t.first,now),t.second);
}
void dfs(Treap *o,Treap *&rt){
if(!o)return ;
dfs(o->ch[],rt);
insert(rt,o->val);
dfs(o->ch[],rt);
}
int find1(Treap *rt,int x){
if(rt==NULL)return ;
if(rt->val>=x)return find1(rt->ch[],x);
else{
if(!rt->ch[]||rt->ch[]->minn>=x)return rt->val;
return find1(rt->ch[],x);
}
}
int find2(Treap *rt,int x){
if(rt==NULL)return ;
if(rt->val<=x)return find2(rt->ch[],x);
else{
if(!rt->ch[]||rt->ch[]->maxn<=x)return rt->val;
return find2(rt->ch[],x);
}
}
void query(Treap *rt,int x,LL &s1,int &s2){
if(!rt)return ;
if(rt->val<=x){
if(rt->ch[])s1+=rt->ch[]->sum1,s2+=rt->ch[]->sum2;
s1+=rt->val1,s2+=rt->val2;
query(rt->ch[],x,s1,s2);
}
else query(rt->ch[],x,s1,s2);
}
LL query(int x,int l){
LL ans=;
int r1=root[x]->minn,r2=root[x]->maxn;
if(r2-l+<r1){
ans+=1ll*(r1-l)*(r1-(r2-l+));
ans+=1ll*(n-(r2-l)-+n-r1)*(r1-r2+l-)/;
}
int pos1=find1(root[x],r2-l+);
int pos2=find2(root[x],r1+l-);
if(!pos2)pos2=r2;
LL sum1=,sum2=;
int size1=,size2=;
query(root[x],pos1,sum1,size1);
query(root[x],pos2,sum2,size2);
if(pos2>pos1){
ans+=sum2-sum1;
ans-=1ll*(r2-l+)*(size2-size1);
if(pos2-l+>r1)ans-=1ll*((pos2-l+)-r1)*(pos2-(r2-l+));
}
return ans;
}
int last[N],tot,mx[N<<],ch[N<<][],par[N<<]; void extend(int x,int c){
int p=last[x-],np=++tot;
mx[np]=mx[p]+;
root[np]=NULL;
insert(root[np],x);
for(;p&&!ch[p][c];p=par[p])ch[p][c]=np;
if(!p) par[np]=;
else{
int q=ch[p][c];
if(mx[q]==mx[p]+)par[np]=q;
else{
int nq=++tot;
par[nq]=par[q];
memcpy(ch[nq],ch[q],sizeof ch[nq]);
mx[nq]=mx[p]+;
root[nq]=NULL;
par[q]=par[np]=nq;
for(;p&&ch[p][c]==q;p=par[p])ch[p][c]=nq;
}
}
last[x]=np;
}
int e=,head[N<<];
struct edge{
int v,next;
}ed[N<<];
void add(int u,int v){
ed[e].v=v;ed[e].next=head[u];
head[u]=e++;
}
int fa[N<<][];
void dfs(int x,int d){
for(int i=;(<<i)<=d;i++)
fa[x][i]=fa[fa[x][i-]][i-];
for(int i=head[x];i;i=ed[i].next){
fa[ed[i].v][]=x;
dfs(ed[i].v,d+);
}
}
int find(int x,int l){
for(int i=;~i;i--)
if(mx[fa[x][i]]>=l)x=fa[x][i];
return x;
}
void dfs(int x){
for(int i=head[x];i;i=ed[i].next){
dfs(ed[i].v);
if(siz(root[ed[i].v])>siz(root[x]))swap(root[x],root[ed[i].v]);
dfs(root[ed[i].v],root[x]);
}
for(int i=;i<V[x].size();i++){
int now=V[x][i];
d[now].ans=query(x,d[now].r-d[now].l+);
}
}
int main(){
scanf("%d%d",&n,&m);
scanf("%s",s+);
last[]=++tot;
for(int i=;i<=n;i++)extend(i,s[i]-'');
for(int i=;i<=tot;i++)add(par[i],i);
dfs(,);
for(int i=,x;i<=m;i++){
scanf("%d%d",&d[i].l,&d[i].r);
x=find(last[d[i].r],d[i].r-d[i].l+);
V[x].push_back(i);
}
dfs();
LL all=1ll*(n-)*(n-)/;
for(int i=;i<=m;i++){
d[i].ans=all-d[i].ans;
printf("%lld\n",d[i].ans);
}
return ;
}