CF587F Duff is Mad

这题如果往根号方面想还是比较容易想到做法的。另外这题可以不带 $\log$ 的！

首先，区间内的串在某个串的出现次数，可以考虑广义 SAM 或者 ACAM。感觉两个东西都可以做这个题，为了复习 ACAM （为了去做上次 edu 的G）写下 ACAM 吧。

我们考虑 $s_{l\dots r}$ 在 $s_k$ 里出现次数这个问题。可以看成 对 $s_x,x\in [l,r]$ 看它在 $s_k$ 的出现次数。这个问题显然是可以前缀和的，也就是 $s_{1\dots r}$ 在 $s_k$ 的出现次数减去 $s_{1\dots l-1}$ 的出现次数。于是我们可以把 $s_k$ 给提出来。设总长度是 $L$ ，这个时候我们就有了两种做法：

• 一个一个字母加入 $s_{1\dots n}$ ，我们设当前加入字母后在 AC 自动机上的节点 $u$ ，我们考虑它是 $s_k$ 所处的一连串节点的多少个节点的祖先。如果它是某个节点的祖先，那么就说明在这个节点的位置在 $s_k$ 中出现了一次。我们可以预处理所有 $s_k$ 的节点的祖先的位置的贡献系数，复杂度是 $O(L)$ 的。
• 直接给 $1\dots n$ 的字符串一个一个把字符串结尾处的子树 + 1，当处理到一个位置，只需要 $O(len_{s_k})$ 跑一下询问串看看这个位置被加了多少次。这样做对于每个询问串的复杂度是 $O(len)$ 的，总共还有个复杂度也就是一个一个 + 1的复杂度。我们可以用 BIT 轻松做到 $O(n\log n)$ ，但是这样查询复杂度也变成了 $O(len \log n)$ 。又可以那根号平衡来优化，加一的时候 $O(\sqrt L)$ ，查询的时候 $O(1)$ 。于是处理一个串的复杂度是 $O(len)$ 的，总复杂度是 $O(qlen + n\sqrt L)$ 。

可以把两个方法合并一下，假设大于 $M$ 的串我们用第一个方法，否则用第二个方法，于是复杂度是$O(\frac {L^2} M + qM + n\sqrt n)$ 可以假设 $q,L$ 同阶，把 $M$ 设到 $\sqrt L$ 复杂度就有了 $O(L\sqrt L + n\sqrt L)$

cpp

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "bitset"
#include "queue"
using namespace std;
#define MAXN 100006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define chkmn( a , b ) ( (a) = ( (a) < (b) ? (a) : (b) ) )
#define chkmx( a , b ) ( (a) = ( (a) > (b) ? (a) : (b) ) )
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
#define P 998244353
typedef long long ll;
int n , q , L , blo;

char ch[MAXN]; int len[MAXN];

int son[MAXN][26] , cnt , bac[MAXN];
vi ns[MAXN];
void ins( char* s , int id ) {
    int len = strlen( s ) , cur = 0;
    rep( i , 0 , len - 1 ) {
        int v = s[i] - 'a';
        if( !son[cur][v] ) son[cur][v] = ++ cnt;
        cur = son[cur][v] , ns[id].pb( cur );
    }
    bac[id] = cur;
}
queue<int> Q;
int fail[MAXN];
void build( ) {
    int u;
    rep( i , 0 , 25 ) if( son[0][i] ) Q.push( son[0][i] );
    while( !Q.empty( ) ) {
        u = Q.front(); Q.pop();
        rep( i , 0 , 25 ) {
            if( son[u][i] )
                fail[son[u][i]] = son[fail[u]][i] , Q.push( son[u][i] );
            else son[u][i] = son[fail[u]][i];
        }
    }
}

vi G[MAXN];
void addall( ) {
    rep( i , 1 , cnt ) G[fail[i]].pb( i );
}

int dfn[MAXN] , R[MAXN] , clo;
void dfs( int u ) {
    dfn[u] = ++ clo;
    for( int& v : G[u] ) dfs( v );
    R[u] = clo;
}

int cn[MAXN];
void work( int u ) {
    for( int& v : G[u] ) work( v ) , cn[u] += cn[v];
}

int BLO;
namespace kuai {
    int T[MAXN] , lz[500];
    void add( int x , int c ) {
        if( !x ) return;
        int w = ( x - 1 ) / BLO; // pervious kuai
        per( i , x , w * BLO + 1 ) T[i] += c;
        rep( i , 1 , w ) lz[i] += c;
    }
    int get( int x ) {
        return T[x] + lz[( x - 1 ) / BLO + 1];
    }
}

struct orzzh {
    int l , r , bp;
};
vector<orzzh> que[MAXN] , quel[MAXN];

long long S[MAXN] , ans[MAXN];
void solve() {
    cin >> n >> q;
    rep( i , 1 , n ) {
        scanf("%s",ch);
        ins( ch , i );
        len[i] = strlen( ch ); L += len[i];
    }
    blo = sqrt( L ); BLO = sqrt( cnt );
    build( );
    int l , r , k;
    rep( i , 1 , q ) {
        scanf("%d%d%d",&l,&r,&k);
        if( len[k] > blo ) {
            que[k].eb( (orzzh) { l , r , i } );
        } else {
            quel[l - 1].eb( (orzzh) { k , -1 , i } );
            quel[r].eb( (orzzh) { k , 1 , i } );
        }
    }
    addall( );
    rep( i , 1 , n ) if( !que[i].empty() ) {
        rep( j , 1 , cnt ) cn[j] = 0 , S[j] = 0;
        for( int x : ns[i] ) ++ cn[x];
        work( 0 );
        rep( j , 1 , n )
            S[j] = S[j - 1] + cn[bac[j]];
        for( auto& t : que[i] ) ans[t.bp] += S[t.r] - S[t.l - 1];
    }
    dfs( 0 );
    rep( i , 1 , n ) {
        kuai::add( R[bac[i]] , 1 ) , kuai::add( dfn[bac[i]] - 1 , -1 );
//        printf("%d %d\n",dfn[bac[i]] , R[bac[i]]);
        for( auto& t : quel[i] ) {
            long long s = 0;
            for( int& x : ns[t.l] ) s += kuai::get( dfn[x] );
            ans[t.bp] += t.r * s;
        }
    }
    rep( i , 1 , q ) printf("%lld\n",ans[i]);
}

signed main() {
//    freopen("input","r",stdin);
//    freopen("fuckout","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}