rt

目测是比答案大了。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>

#define N 200001
#define LL long long

using namespace std;
int n,q;
string s;

int tcnt,rt[N];
struct Tree { int ls,rs,mn,mx; LL sum1,sum2; }t[N<<6];

Tree pushup(Tree a,Tree b) {
    return {0,0,min(a.mn,b.mn),max(a.mx,b.mx),
        a.sum1+b.sum1+(b.mn!=1e9 and a.mx?1ll*(b.mn-a.mx)*b.mn:0),
        a.sum2+b.sum2+(b.mn!=1e9 and a.mx?b.mn-a.mx:0)};
}

void upd(int &x,int l,int r,int pos) {
    if (!x) x=++tcnt;
    if (l==r) return t[x]={0,0,l,l,0,0},void();
    int mid=(l+r>>1);
    if (pos<=mid) upd(t[x].ls,l,mid,pos);
    else upd(t[x].rs,mid+1,r,pos);
    t[x].mn=min(t[t[x].ls].mn,t[t[x].rs].mn);
    t[x].mx=max(t[t[x].ls].mx,t[t[x].rs].mx);
    t[x].sum1=t[t[x].ls].sum1+t[t[x].rs].sum1
                +(t[t[x].rs].mn!=1e9 and t[t[x].ls].mx?1ll*(t[t[x].rs].mn-t[t[x].ls].mx)*t[t[x].rs].mn:0);
    t[x].sum2=t[t[x].ls].sum2+t[t[x].rs].sum2
                +(t[t[x].rs].mn!=1e9 and t[t[x].ls].mx?t[t[x].rs].mn-t[t[x].ls].mx:0);
}

int merge(int x,int y,int l,int r) {
    if (!x or !y) return x|y;
    int rt=++tcnt;
    if (l==r) return t[rt]={0,0,l,l,0,0},rt;
    int mid=(l+r>>1);
    t[rt].ls=merge(t[x].ls,t[y].ls,l,mid);
    t[rt].rs=merge(t[x].rs,t[y].rs,mid+1,r);
    t[rt].mn=min(t[t[rt].ls].mn,t[t[rt].rs].mn);
    t[rt].mx=max(t[t[rt].ls].mx,t[t[rt].rs].mx);
    t[rt].sum1=t[t[rt].ls].sum1+t[t[rt].rs].sum1
                +(t[t[rt].rs].mn!=1e9 and t[t[rt].ls].mx?1ll*(t[t[rt].rs].mn-t[t[rt].ls].mx)*t[t[rt].rs].mn:0);
    t[rt].sum2=t[t[rt].ls].sum2+t[t[rt].rs].sum2
                +(t[t[rt].rs].mn!=1e9 and t[t[rt].ls].mx?t[t[rt].rs].mn-t[t[rt].ls].mx:0);
    return rt;
}

Tree ask(int x,int l,int r,int L,int R) {
    if (!x or L>R) return t[0];
    if (L<=l and r<=R) return t[x];
    int mid=(l+r>>1);
    if (R<=mid) return ask(t[x].ls,l,mid,L,R);
    else if (L>mid) return ask(t[x].rs,mid+1,r,L,R);
    else return pushup(ask(t[x].ls,l,mid,L,R),ask(t[x].rs,mid+1,r,L,R));
}

int tot=1,np=1,ch[N][10],len[N],fail[N],pos[N];

void ins(int c,int Pos) {
    int p=np; len[pos[Pos]=np=++tot]=len[p]+1;
    upd(rt[np],1,n,Pos);
    while (p and !ch[p][c]) ch[p][c]=np,p=fail[p];
    if (!p) fail[np]=1;
    else {
        int q=ch[p][c];
        if (len[q]==len[p]+1) fail[np]=q;
        else {
            int nq=++tot;
            len[nq]=len[p]+1,fail[nq]=fail[q];
            fail[q]=fail[np]=nq;
            memcpy(ch[nq],ch[q],sizeof ch[q]);
            while (p and ch[p][c]==q) ch[p][c]=nq,p=fail[p];
        }
    }
}

int cnt,head[N];
struct Node { int to,nxt; }e[N];

void add(int u,int v) { e[++cnt]=Node{v,head[u]},head[u]=cnt; }

int fa[N][20];

void dfs0(int u) {
    fa[u][0]=fail[u];
    for (int i=1;i<20;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for (int i=head[u];i;i=e[i].nxt) {
        int v=e[i].to;
        dfs0(v);
        rt[u]=merge(rt[u],rt[v],1,n);
    }
}

int main() {
    scanf("%d%d",&n,&q);
    cin>>s;
    t[0]={0,0,(int)1e9,0,0,0};
    for (int i=0;i<n;i++) ins(s[i]-'0',i+1);
    for (int i=2;i<=tot;i++) add(fail[i],i);
    dfs0(1);
    for (int i=1,l,r;i<=q;i++) {
        scanf("%d%d",&l,&r);
        if (l>r or l<1 or l>n or r<1 or r>n) {
            printf("%lld\n",1ll*(n-1)*(n-2)/2);
            continue;
        }
        int p=pos[r];
        for (int i=19;i>=0;i--)
            while (len[fa[p][i]]>=r-l+1) p=fa[p][i];
        int mn=t[rt[p]].mn,mx=t[rt[p]].mx;
        LL sum1=t[rt[p]].sum1,sum2=t[rt[p]].sum2;
        Tree tmp1=ask(rt[p],1,n,mx-(r-l),mn+(r-l)),
            tmp2=ask(rt[p],1,n,mn,mx-(r-l+1)),
            tmp3=ask(rt[p],1,n,1,mn+(r-l)),
            tmp4=ask(rt[p],1,n,mn+(r-l)+1,n);
        if (tmp2.mx and tmp2.mx-mn>=r-l+1 and mx-tmp2.mx>=r-l+1) printf("%lld\n",1ll*(n-1)*(n-2)/2);
        else if (mn>=mx-(r-l)) 
            printf("%lld\n",1ll*(n-1)*(n-2)/2-(sum1-sum2*(mx-(r-l))
                +1ll*(mn-(mx-(r-l)))*(mn-(mx-(r-l))-1)/2
                +1ll*(mn-(mx-(r-l)))*(n-(r-l+1))));
        else
            printf("%lld\n",1ll*(n-1)*(n-2)/2-(tmp1.sum1-tmp1.sum2*(mx-(r-l))
                +(tmp4.mn>(mx-(r-l))?1ll*(mn-(tmp3.mx-(r-l)))*(tmp4.mn-(mx-(r-l))):0)));
    }
    return 0;
}