Luogu

LOJ

分析

首先容斥一下，求出三段都不包含 $s_{l..r}$ 的方案数，然后用 ${n-1\choose 2}$ 减掉即为答案。

我们先把所有和 $s_{l..r}$ 相等的子串位置都找到，然后分类讨论一下：

• 如果有三个互不相交的串，方案数是 $0$。
• 如果最左边的串和最右边的串相交：
  
  考虑 $i$ 的位置：
  • 如果 $i\in[1,l_1)$，那么 $j\in(l_m,r_1]$，方案数为 $(l_1-1)(r_1-l_m)$。
  • 如果 $i\in[l_i,l_{i+1})$，那么 $j\in(l_m,r_{i+1}]$，方案数为 $\sum_{i=1}^{m-1}(r_{i+1}-r_i)(r_{i+1}-l_m)$。
  • 如果 $i\in[l_m,r_1)$，那么只要有 $i+1<j$，方案数为 ${r_1-l_m\choose 2}+(r_1-l_m)(n-r_1)$。
  • 如果 $i\in[r_1,n]$，方案数为 $0$。
• 如果最左边的串不和最右边的串相交：
  
  仍然考虑 $i$ 的位置：
  • 如果 $i\in[1,l_1)$，方案数为 $0$。
  • 如果 $i\in[l_i,l_{i+1})$，方案数不为 $0$ 当且仅当 $l_m<r_{i+1}$ 且 $l_{i+1}<r_1$，此时方案数为 $(r_{i+1}-r_i)(r_{i+1}-l_m)$。
  • 如果 $i\in[l_?,r_1)$，那么找到 $r_1+len-1$ 的前驱 $p$ 和后继 $q$，方案数为 $(r_1-l_p)(r_q-l_m)$。

具体实现时，我们先建 SAM，然后求出 Parent 树及树上倍增数组，并在 Parent 树上用线段树合并求出每个节点的 $endpos$ 集合。对于询问，我们先倍增跳到 $s_{l..r}$ 所在的节点 $u$，然后根据不同的情况算方案数。

判断是否有 $3$ 个互相不交的子串可以求出最靠左的和最靠右的位置，然后判断中间是否有一个。在算第三种情况时，需要找到最大的 $r_i\leq l_m$，以及 $r_1+len-1$ 的前驱和后继。我们只需要在线段树上维护区间 $endpos$ 集合的最小值、最大值即可完成上述操作。为了计数，我们还需要维护 $\sum(r_{i+1}-r_i)r_{i+1}$ 和 $\sum(r_{i+1}-r_i)$。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;
const int inf=0x3f3f3f3f;

int n,Q; char s[N];

#define ls(o) ch[o][0]
#define rs(o) ch[o][1]
namespace T {
    int rt[N],tot=0;
    int ch[N*30][2];
    struct node {
        int mn,mx; ll s1,s2;
        node(int mn_=inf,int mx_=0,ll s1_=0,ll s2_=0): mn(mn_),mx(mx_),s1(s1_),s2(s2_) {}
    } t[N*30];

    node operator +(node a,node b) {
        if (!a.mx) return b;
        if (!b.mx) return a;
        return node(min(a.mn,b.mn),max(a.mx,b.mx),
                    a.s1+b.s1+1ll*(b.mn-a.mx)*b.mn,
                    a.s2+b.s2+b.mn-a.mx);
    }

    void pushup(int o) { t[o]=t[ls(o)]+t[rs(o)]; }

    void modify(int &o,int l,int r,int p) {
        if (!o) o=++tot;
        if (l==r) { t[o]=node(p,p,0,0); return; }
        int mid=(l+r)>>1;
        if (p<=mid) modify(ls(o),l,mid,p);
        else modify(rs(o),mid+1,r,p);
        pushup(o);
    }
    int qmin(int o,int l,int r,int ql,int qr) {
        if (!o) return inf;
        if (ql<=l&&r<=qr) return t[o].mn;
        int mid=(l+r)>>1,res=inf;
        if (ql<=mid) res=min(res,qmin(ls(o),l,mid,ql,qr));
        if (qr>mid) res=min(res,qmin(rs(o),mid+1,r,ql,qr));
        return res;
    }
    int qmax(int o,int l,int r,int ql,int qr) {
        if (!o) return 0;
        if (ql<=l&&r<=qr) return t[o].mx;
        int mid=(l+r)>>1,res=0;
        if (ql<=mid) res=max(res,qmax(ls(o),l,mid,ql,qr));
        if (qr>mid) res=max(res,qmax(rs(o),mid+1,r,ql,qr));
        return res;
    }
    node query(int o,int l,int r,int ql,int qr) {
        if (!o) return node();
        if (ql<=l&&r<=qr) return t[o];
        int mid=(l+r)>>1; node res;
        if (ql<=mid) res=res+query(ls(o),l,mid,ql,qr);
        if (qr>mid) res=res+query(rs(o),mid+1,r,ql,qr);
        return res;
    }

    int merge(int x,int y) {
        if (!x||!y) return x|y;
        int o=++tot;
        ls(o)=merge(ls(x),ls(y)),rs(o)=merge(rs(x),rs(y));
        pushup(o); return o;
    }
}
#undef ls
#undef rs
using T::rt;

namespace S {
    int last,cnt;
    int fa[N],ch[N][10],len[N],pos[N];

    void extend(int c) {
        int p=last,np=++cnt; last=np,len[np]=len[p]+1;
        for (;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
        if (!p) fa[np]=1;
        else {
            int q=ch[p][c];
            if (len[p]+1==len[q]) fa[np]=q;
            else {
                int nq=++cnt; len[nq]=len[p]+1;
                memcpy(ch[nq],ch[q],sizeof(ch[q]));
                fa[nq]=fa[q],fa[q]=fa[np]=nq;
                for (;ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
            }
        }
    }

    int f[18][N];
    vector<int> E[N];
    void dfs(int u) {
        f[0][u]=fa[u];
        for (int i=1;i<=17;++i) f[i][u]=f[i-1][f[i-1][u]];
        for (int v:E[u]) dfs(v),rt[u]=T::merge(rt[u],rt[v]);
    }

    void init() {
        last=cnt=1;
        for (int i=1;i<=n;++i) extend(s[i]-'0'),pos[i]=last;
        for (int i=2;i<=cnt;++i) E[fa[i]].emplace_back(i);
        for (int i=1;i<=n;++i) T::modify(rt[pos[i]],1,n,i);
        dfs(1);
    }

    int jump(int u,int l) {
        for (int i=17;~i;--i)
            if (len[f[i][u]]>=l) u=f[i][u];
        return u;
    }
}

ll C2(int n) { return 1ll*n*(n-1)/2; }

int main() {
    n=read(),Q=read(); scanf("%s",s+1);
    S::init();
    while (Q--) {
        int l=read(),r=read(),len=r-l+1,u=S::jump(S::pos[r],len);
        int r1=T::qmin(rt[u],1,n,1,n),rm=T::qmax(rt[u],1,n,1,n),lm=rm-len+1;
        ll ans;
        if (r1+len*2-1<rm&&r1+len-1<T::qmax(rt[u],1,n,r1+1,rm-len)) ans=0;
        else if (lm<=r1) {
            auto t=T::query(rt[u],1,n,1,n); int lm=rm-len+1;
            ans=t.s1-t.s2*lm+C2(r1-lm)+1ll*(r1-lm)*(n-len);
        } else {
            int p=T::qmax(rt[u],1,n,1,lm);
            auto t=T::query(rt[u],1,n,p,r1+len-1);
            int lp=T::qmax(rt[u],1,n,1,r1+len-1)-len+1;
            int rq=T::qmin(rt[u],1,n,r1+len,n);
            ans=t.s1-t.s2*lm+(rq>lm?1ll*(r1-lp)*(rq-lm):0);
        }
        printf("%lld\n",C2(n-1)-ans);
    }
    return 0;
}