为了求解这个问题，我们先考虑「静态区间不同元素种类数」的经典问题。下面是这个问题的一种常见解法：

对于一个固定的右端点 i，贪心地只考虑 i 之前每种元素最后出现的位置。按下标从左到右扫描线，用一棵线段树维护每个位置是否在前缀 i 种最后一次出现。加入第 i 个元素时，在线段树中把当前位置 +1，把上一个相同元素的位置 -1。询问直接区间查询即可。

对于这道题我们采用相同的思路。把本质相同的子串看作同一种元素，那么插入位置 i 时应该在线段树中加入所有以 i 结尾的子串的贡献。子串是有长度的，但我们只需维护左端点即可。那么「在线段树中把当前位置 +1」可以直接一次区间修改来完成，而把「上一个相同元素的位置 -1」目前来看不太好做，因为我们还不知道每个子串上一次出现的位置。

为了解决这个问题，我们对原串建立后缀自动机。那么以 i 结尾的子串就是前缀 i 对应的节点在 parent 树上的所有祖先节点。由同一个状态表示的子串，它们「上一次出现的位置」的右端点是相同的，而左端点是连续的一段，所以我们可以通过暴力跳 parent 树上祖先并在线段树上区间修改来达到目的。同时还需要把这条链上的节点都染成 i 颜色，表示把这些子串最后一次出现的位置修改为 i。但这样做的复杂度显然是不对的，需要寻求更优的方法。

发现颜色相同的节点的节点会连成一段，我们可以将它们一起处理。由于只有「将某一点到根节点的颜色染成一种没有出现过的颜色」这一种操作，所有需要处理的链上的总颜色数实际上是 O(n\log n) 的。原因是染色操作其实对应着 LCT 的 \text{Access} 操作，可以套用其复杂度证明方法。所以在实现时我们也可以直接使用 LCT 来维护，因为一条实链上的颜色一定都是相同的，直接模拟 \text{Access} 的过程即可。

复杂度是 LCT 的复杂度加上线段树的复杂度，为 O(n\log^2n+q\log n)。如果要求在线就上可持久化吧。

下面是两道选做的题目：

• 树点涂色 这道题对最后一段的理解会有很大启发；
• 事情的相似度 一道可以用类似 Trick 解决的题目。

然后是这道题代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN=220000;
int n, q;
char s[MAXN];
namespace SAM
{
    struct Node
    {
        int nxt[26], fail, len;
    } st[MAXN];
    int m, root, lst;
    int pos[MAXN];
    inline int newNode(int l)
    {
        m++;
        memset(st[m].nxt, 0, sizeof st[m].nxt);
        st[m].fail=0, st[m].len=l;
        return m;
    }
    void extend(int x)
    {
        int p=lst, np=newNode(st[p].len+1); lst=np;
        while (p&&!st[p].nxt[x]) st[p].nxt[x]=np, p=st[p].fail;
        if (!p) { st[np].fail=root; return; }
        int q=st[p].nxt[x]; if (st[q].len==st[p].len+1) { st[np].fail=q; return; }
        int nq=newNode(st[p].len+1); memcpy(st[nq].nxt, st[q].nxt, sizeof st[q].nxt);
        st[nq].fail=st[q].fail; st[np].fail=st[q].fail=nq;
        while (p&&st[p].nxt[x]==q) st[p].nxt[x]=nq, p=st[p].fail;
    }
    void build()
    {
        m=0; lst=root=newNode(0);
        for (int i=1; i<=n; i++)
            extend(s[i]-'a'), pos[i]=lst;
    }
}
namespace SGT
{
    struct Node
    {
        int l, r;
        ll sum; int add;
    } tr[4*MAXN];
    #define lc (o<<1)
    #define rc (o<<1|1)
    inline void pushup(int o)
    {
        tr[o].sum=tr[lc].sum+tr[rc].sum;
    }
    inline void add(int o, int k)
    {
        tr[o].sum+=1ll*k*(tr[o].r-tr[o].l+1);
        tr[o].add+=k;
    }
    inline void pushdown(int o)
    {
        if (tr[o].add)
        {
            add(lc, tr[o].add);
            add(rc, tr[o].add);
            tr[o].add=0;
        }
    }
    void build(int o, int l, int r)
    {
        tr[o].l=l, tr[o].r=r;
        tr[o].sum=tr[o].add=0;
        if (l==r) return;
        int mid=l+r>>1;
        build(lc, l, mid), build(rc, mid+1, r);
    }
    void modify(int o, int l, int r, int k)
    {
        if (tr[o].l>r||tr[o].r<l) return;
        if (l<=tr[o].l&&tr[o].r<=r) { add(o, k); return; }
        pushdown(o);
        modify(lc, l, r, k), modify(rc, l, r, k);
        pushup(o);
    }
    ll query(int o, int l, int r)
    {
        if (tr[o].l>r||tr[o].r<l) return 0;
        if (l<=tr[o].l&&tr[o].r<=r) return tr[o].sum;
        pushdown(o);
        return query(lc, l, r)+query(rc, l, r);
    }
    #undef lc
    #undef rc
}
namespace LCT
{
    struct Node
    {
        int val, cov;
        int fa, c[2];
    } tr[MAXN];
    #define lc tr[x].c[0]
    #define rc tr[x].c[1]
    #define par tr[x].fa
    inline bool isroot(int x)
    {
        return tr[par].c[0]!=x&&tr[par].c[1]!=x;
    }
    inline void cover(int x, int k)
    {
        tr[x].val=tr[x].cov=k;
    }
    inline void pushdown(int x)
    {
        if (tr[x].cov)
        {
            if (lc) cover(lc, tr[x].cov);
            if (rc) cover(rc, tr[x].cov);
            tr[x].cov=0;
        }
    }
    inline bool getlr(int x)
    {
        return tr[par].c[1]==x;
    }
    inline void rotate(int x)
    {
        int y=par, z=tr[y].fa;
        bool k=getlr(x); int w=tr[x].c[!k];
        if (!isroot(y)) tr[z].c[getlr(y)]=x; par=z;
        tr[y].c[k]=w; if (w) tr[w].fa=y;
        tr[x].c[!k]=y; tr[y].fa=x;
    }
    void pushall(int x)
    {
        if (!isroot(x)) pushall(par);
        pushdown(x);
    }
    void splay(int x)
    {
        pushall(x);
        while (!isroot(x))
        {
            if (!isroot(par)) rotate(getlr(x)^getlr(par)?x:par);
            rotate(x);
        }
    }
    void access(int x, int p)
    {
        int y=0;
        while (x)
        {
            splay(x);
            if (int k=tr[x].val)
                SGT::modify(1, k-SAM::st[x].len+1, k-SAM::st[par].len, -1);
            rc=y, y=x, x=par;
        }
        cover(y, p);
        SGT::modify(1, 1, p, 1);
    }
    void build()
    {
        for (int i=2; i<=SAM::m; i++)
        {
            tr[i].val=tr[i].cov=0;
            tr[i].c[0]=tr[i].c[1]=0;
            tr[i].fa=SAM::st[i].fail;
        }
    }
    #undef lc
    #undef rc
    #undef par
}
struct Query
{
    int l, r, id;
    bool operator < (const Query& rhs) const
    {
        return r<rhs.r;
    }
} a[MAXN];
ll ans[MAXN];
int main()
{
//  freopen("P6292.in", "r", stdin);
//  freopen("P6292.out", "w", stdout);
    scanf("%s", s+1), n=strlen(s+1);
    SAM::build();
    LCT::build();
    scanf("%d", &q);
    for (int i=1; i<=q; i++)
    {
        scanf("%d%d", &a[i].l, &a[i].r);
        a[i].id=i;
    }
    sort(a+1, a+q+1);
    SGT::build(1, 1, n);
    for (int i=1, j=1; i<=q; i++)
    {
        while (j<=a[i].r)
            LCT::access(SAM::pos[j], j), j++;
        ans[a[i].id]=SGT::query(1, a[i].l, a[i].r);
    }
    for (int i=1; i<=q; i++) printf("%lld\n", ans[i]);
    return 0;
}