调调改改了一晚上才过掉。总而言之还是自己对题目理解太不深刻了。基本上是对着抄但是又抄得很无奈。

Solution

不考虑区间限制的话，则 $S, T$ 同时匹配。如果 $S$ 向 $c$ 边转移出现了不匹配，那么将 $S$ 向上跳到匹配为止，同时 $T$ 也应该向上跳使得 $len$ 与现处的状态相符。

考虑区间限制的话，我们使用线段树合并维护树的 $endpos$ 集合。那么对于已经固定了的字符串长度 $l’$ ，需要加上字符 $c$ ，要求 $S$ 转移后所处状态的 $endpos$ 存在于 $[l+l’, r]$ 。否则我们需要将 $l’$ 一步步减小 来查看是否匹配。当 $l’=len[fa[p]]$ 时需要将 $p$ 向上转移。

我们同时需要意识到我们可以在 $S$ 的 parent 树上直接转移，且转移到的节点的 $len$ 是符合假想区间 parent 树构造的（或者略大，但如果向上跳一定符合），因为我们转移到的状态一定在区间 parent 树上存在。这部分我觉得我可能还需要再加深理解。

口胡一下：对于SAM，如果从状态 $A$ 转移到状态 $B$ ，你需要保证如下条件：$endpos$ 集合存在，且 $len’$ 属于结点所属 $len$ 区间。由于 $len’=len+1$ ，所以只需要保证 $endpos$ 合法即可。

Code

// Code by ajcxsu
// Problem: yourname.

#include<bits/stdc++.h>
using namespace std;

const int N=3e6+10, M=5e7+10;
struct Node {
    int ch[26];
    int len, fa;
    void clr() { len=fa=0; memset(ch, 0, sizeof(ch)); }
} ;

struct Tree *nil;
struct Tree {
    int v, t;
    Tree *ls, *rs;
} po[M], *pp=po;
void ini() { nil=pp++; nil->ls=nil->rs=nil; }
Tree* newn() { assert(pp!=po+M), *pp=*nil; return pp++; }
void updata(Tree *&x, int l, int r, int d) {
    if(x==nil) x=newn();
    x->v=max(x->v, d); if(l==r) return;
    int mid=(l+r)>>1;
    if(d<=mid) updata(x->ls, l, mid, d);
    else updata(x->rs, mid+1, r, d);
}
Tree* Merge(Tree *x, Tree *y) {
    Tree *o=newn(); if(x==nil || y==nil) return x==nil?y:x;
    o->v=max(x->v, y->v);
    o->ls=Merge(x->ls, y->ls), o->rs=Merge(x->rs, y->rs);
    return o;
}
int query(Tree *x, int l, int r, int xr) {
    if(r<=xr) return x->v;
    int mid=(l+r)>>1, ret=query(x->ls, l, mid, xr);
    if(xr>mid) ret=max(ret, query(x->rs, mid+1, r, xr));
    return ret;
}
typedef long long ll;
struct SAM {
    Node nd[N];
    int idx=1, lst=1;
    int g[N]; Tree *tr[N];
    void add(int c, int mode) {
        int p=lst, np=lst=++idx; nd[np].clr(), nd[np].len=nd[p].len+1;
        if(mode) updata(tr[idx], 0, N, nd[np].len);
        for(; p && !nd[p].ch[c]; p=nd[p].fa) nd[p].ch[c]=np;
        if(!p) nd[np].fa=1;
        else {
            int q=nd[p].ch[c];
            if(nd[q].len==nd[p].len+1) nd[np].fa=q;
            else {
                int nq=++idx; nd[nq]=nd[q];
                nd[nq].len=nd[p].len+1, nd[q].fa=nd[np].fa=nq;
                for(; p && nd[p].ch[c]==q; p=nd[p].fa) nd[p].ch[c]=nq;
            }
        }
    }
    int id[N], bu[N];
    void sort() {
        fill(bu, bu+idx+1, 0); // !!
        for(int i=1; i<=idx; i++) bu[nd[i].len]++;
        for(int i=1; i<=idx; i++) bu[i]+=bu[i-1];
        for(int i=idx; i>=1; i--) id[bu[nd[i].len]--]=i;
    }
    ll ftot;
    void ini1() {
        for(int i=idx; i>=2; i--) ftot+=nd[i].len-nd[nd[i].fa].len;
    }
    void ini2() {
        for(int i=idx; i>=2; i--) {
            int tmp=id[i];
            tr[nd[tmp].fa]=Merge(tr[nd[tmp].fa], tr[tmp]);
        }
    }
    char str[N];
    int n;
    void ini(int mode=0) {
        idx=lst=1; ftot=0;
        n=strlen(str);
        if(mode) fill(tr, tr+N, nil);
        nd[1].clr();
        for(int i=0; i<n; i++) add(str[i]-'a', mode);
        sort();
        fill(g, g+idx+1, 0);
        if(!mode) ini1();
        else ini2();
    }
    ll deal() {
        ll cnt=0;
        for(int i=idx; i>=2; i--) {
            int tmp=id[i];
            g[tmp]=min(g[tmp], nd[tmp].len);
            g[nd[tmp].fa]=max(g[nd[tmp].fa], g[tmp]);
            cnt+=max(g[tmp]-nd[nd[tmp].fa].len, 0); // 忘取max了...
        }
        return ftot-cnt;
    }
    inline int mov(int x, char ch) { return nd[x].ch[ch-'a']; }
} s, t;

int main() {
    ini();
    scanf("%s", s.str);
    s.ini(1);
    int T; scanf("%d", &T);
    int l, r;
    while(T--) {
        scanf("%s%d%d", t.str, &l, &r);
        t.ini();
        int na=1, nb=1, len=0, to;
        bool chg;
        for(int i=0; i<t.n; i++) {
            to=s.mov(na, t.str[i]);
            nb=t.mov(nb, t.str[i]);
            chg=0;
            while(na && (!to || query(s.tr[to], 0, N, r)<l+len)) {
                if(!len) { na=0; break; }
                len--;
                if(len==s.nd[s.nd[na].fa].len) na=s.nd[na].fa, to=s.mov(na, t.str[i]);
            }
            if(!na) na=1, len=0;
            else na=to, len++;
            while(nb && t.nd[t.nd[nb].fa].len>=len) nb=t.nd[nb].fa;
            nb+=!nb;
            t.g[nb]=max(t.g[nb], len);
        }
        printf("%lld\n", t.deal());
    }
    return 0;
}