Duff is Mad

无内鬼，来一发和 ACAM 解法并无本质区别的 SAM 解法（

首先把询问差分成两个参数 \(r,k\)，并考虑两个子问题：

若每次询问的 \(|s_k|\) 之和较小。

将询问对 \(r\) 排序，在 Parent Tree 上把每个 \(s_i\ (i \le r)\) 对应的状态的子树加一，枚举 \(s_k\) 每个前缀对应的状态并求和。
相当于反向统计 \(|{\rm endpos}|\) 之和 —— 计算每个结束位置上有多少串造成贡献。
若 \(q\) 较小。

将所有 \(s_k\) 的每个前缀对应的状态在 Parent Tree 上加一，并求子树和，即求每个状态在每个 \(s_k\) 中的的 \(|{\rm endpos}|\)。
同样将询问对 \(r\) 排序，对每个 \(s_i\ (i \le r)\) 对应的状态求其在 \(s_k\) 中的 \(|{\rm endpos}|\) 之和。

考虑设一个阈值 \(T\)，若询问的 \(|s_k| \le T\)，则做第一个子问题，否则做第二个子问题。
若忽略第一个子问题中数据结构的复杂度，两部分复杂度分别为 \(O\left(nT + \frac{n^2}T\right)\)（假设 \(n,q,\sum|s_i|\) 同阶）。
显然当 \(T = O(\sqrt n)\) 时取最优复杂度 \(O(n \sqrt n)\)。

再来考虑第一个子问题中的数据结构，注意到共有 \(O(n)\) 次修改和 \(O(n \sqrt n)\) 次查询，使用分块做到 \(O(\sqrt n)\) 单次修改和 \(O(1)\) 单次查询即可。
总复杂度依然为 \(O(n \sqrt n)\)（时空常数极大）。

代码：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5;
const int LIM = 430;
const int CNT = N / LIM + 2;
int n,m,m_lim,q,lim = LIM;
int len[N + 5],slen[N + 5],ed[N + 5];
int vis[N + 5],cnt;
char s[N + 5];
long long sum[CNT + 5],ans[N + 5];
struct s_query
{
    int r,k,w,id;
    inline bool operator<(const s_query &o) const
    {
        return r < o.r;
    }
} qry[(N << 1) + 5],qry_lim[(N << 1) + 5];
namespace SAM
{
    struct node
	{
        int ch[26];
        int fa,len;
    } sam[(N << 1) + 5];
    int las = 1,tot = 1;
    int c[N + 5],a[(N << 1) + 5];
    int sz[(N << 1) + 5][CNT + 5];
    inline void insert(int x)
	{
        if(sam[las].ch[x])
        {
            int cur = las,q = sam[cur].ch[x];
            if(sam[cur].len + 1 == sam[q].len)
                las = q;
            else
            {
                int nxt = ++tot;
                sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[q].fa = nxt;
                for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
                    sam[cur].ch[x] = nxt;
                las = nxt;
            }
            return ;
        }
        int cur = las,p = ++tot;
        sam[p].len = sam[cur].len + 1;
        for(;cur && !sam[cur].ch[x];cur = sam[cur].fa)
            sam[cur].ch[x] = p;
        if(!cur)
            sam[p].fa = 1;
        else
        {
            int q = sam[cur].ch[x];
            if(sam[cur].len + 1 == sam[q].len)
                sam[p].fa = q;
            else
            {
                int nxt = ++tot;
                sam[nxt] = sam[q],sam[nxt].len = sam[cur].len + 1,sam[p].fa = sam[q].fa = nxt;
                for(;cur && sam[cur].ch[x] == q;cur = sam[cur].fa)
                    sam[cur].ch[x] = nxt;
            }
        }
        las = p;
    }
    inline void build()
	{
        for(register int i = 1;i <= tot;++i)
            ++c[sam[i].len];
        for(register int i = 1;i <= N;++i)
            c[i] += c[i - 1];
        for(register int i = tot;i > 1;--i)
            a[c[sam[i].len]--] = i;
        for(register int i = tot;i > 1;--i)
            for(register int j = 1;j <= cnt;++j)
                sz[sam[a[i]].fa][j] += sz[a[i]][j];
    }
}
namespace BLOCK
{
    const int N = 2e5;
    const int BLK = 450;
    const int CNT = N / BLK + 2;
    int n,block = BLK,pos[N + 5];
    int pre[CNT + 5],sum[N + 5];
    inline void init()
	{
        n = SAM::tot;
        for(register int i = 1;i <= n;++i)
            pos[i] = (i - 1) / block + 1;
    }
    inline void update(int x,int k)
	{
        if(x > n)
            return ;
        for(register int i = pos[x];i <= pos[n];++i)
            pre[i] += k;
        for(register int i = x;i <= min(pos[x] * block,n);++i)
            sum[i] += k;
    }
    inline void update(int l,int r,int k)
	{
        update(l,k),update(r + 1,-k);
    }
    inline int query(int x)
	{
        return pre[pos[x] - 1] + sum[x];
    }
}
namespace TREE
{
    int to[(N << 1) + 5],pre[(N << 1) + 5],first[(N << 1) + 5];
    inline void add(int u,int v)
	{
        static int tot = 0;
        to[++tot] = v,pre[tot] = first[u],first[u] = tot;
    }
    int sz[(N << 1) + 5],id[(N << 1) + 5];
    void dfs(int p)
	{
        static int tot = 0;
        id[p] = ++tot,sz[p] = 1;
        for(register int i = first[p];i;i = pre[i])
            dfs(to[i]),sz[p] += sz[to[i]];
    }
    inline void init()
	{
        for(register int i = 2;i <= SAM::tot;++i)
            add(SAM::sam[i].fa,i);
        dfs(1);
    }
}
int main()
{
    scanf("%d%d",&n,&q);
    for(register int i = 1;i <= n;++i)
        scanf("%s",s + slen[i - 1] + 1),slen[i] = slen[i - 1] + (len[i] = strlen(s + slen[i - 1] + 1));
    for(register int i = 1;i <= n;++i)
    {
        len[i] > lim && (vis[i] = ++cnt),SAM::las = 1;
        for(register int j = 1;j <= len[i];++j)
            SAM::insert(s[slen[i - 1] + j] - 'a'),ed[slen[i - 1] + j] = SAM::las,vis[i] && ++SAM::sz[SAM::las][cnt];
    }
    SAM::build(),BLOCK::init(),TREE::init();
    int l,r,k;
    for(register int i = 1;i <= q;++i)
    {
        scanf("%d%d%d",&l,&r,&k);
        if(vis[k])
            qry_lim[++m_lim] = (s_query){r,vis[k],1,i},qry_lim[++m_lim] = (s_query){l - 1,vis[k],-1,i};
        else
            qry[++m] = (s_query){r,k,1,i},qry[++m] = (s_query){l - 1,k,-1,i};
    }
    sort(qry + 1,qry + m + 1),sort(qry_lim + 1,qry_lim + m_lim + 1);
    for(register int i = 1,r = 1;i <= m;++i)
    {
        for(;r <= qry[i].r;++r)
            BLOCK::update(TREE::id[ed[slen[r]]],TREE::id[ed[slen[r]]] + TREE::sz[ed[slen[r]]] - 1,1);
        for(register int j = 1;j <= len[qry[i].k];++j)
            ans[qry[i].id] += qry[i].w * BLOCK::query(TREE::id[ed[slen[qry[i].k - 1] + j]]);
    }
    for(register int i = 1,r = 1;i <= m_lim;++i)
    {
        for(;r <= qry_lim[i].r;++r)
            for(register int j = 1;j <= cnt;++j)
                sum[j] += SAM::sz[ed[slen[r]]][j];
        ans[qry_lim[i].id] += qry_lim[i].w * sum[qry_lim[i].k];
    }
    for(register int i = 1;i <= q;++i)
        printf("%lld\n",ans[i]);
}

『My guiding star.』

Codeforces 587F Duff is Mad