题解：P8571 [JRKSJ R6] Dedicatus545

_gghack_ · 2026-10-21 16:18:43 · 题解

前言：

写了一上午加半个下午，只能说你先把思路理清楚就不会像我这样子犹豫太久。

分析：

先考虑一下如果不同的 k 很少我会怎么做。对每个 k 直接做 AC 自动机上的多模匹配就行。这个东西就是 AC 自动机模板。

加上原问题的限制，如果 s_k\ge B 的话，那么不同的 k 至多只有 \frac{\sum\vert s_i\vert}{B} 个，直接按照 AC 自动机模板写一遍，在固定 k 下求出每个 i 的 w(s_i,s_k) 即可。用线段树可以做到快速回答固定 k 下的询问。不用 ST 表是因为建立 ST 表会导致复杂度变成 n\sqrt{n} \log n。

现在重点在这个 s_k < B 怎么做，发现这部分 s_k 插入 AC 自动机的节点数量很小，启发我们对着 AC 自动机本身的形态去考虑。如果你知道 AC 自动机统计模式串出现次数的暴力的话，你发现，如果我建立出来一棵 fail 树，s_i 出现在 s_k 内部，当且仅当这个 s_i 的结束位置，在 fail 树上是 s_k 的某个位置作为结束位置的祖先。（有点拗口，这个某个位置作为结束位置就是对 s_{k,r} 的 r 扫描线，每次考虑每个 r 对应共一段后缀的答案。）

那现在我就有个大概思路，你把 s_i 全部插入 AC 自动机，然后对于一个 s_k，你在 s_{k,r} 的每个结尾打计数标记，最后在 fail 树上面 pushup 这个标记，就可以表示子串关系了。如果我能搞到 s_{k,r} 的每个结尾在 AC 自动机上对应的出现位置，我就能快速回答某个询问。当然别忘了 s_i 的区间限制。

这个你直接对 r 扫描线，设 s_i 的结束位置在 AC 自动机上节点编号为 u，用数据结构对 u 的子树做一次编号覆盖 max，查询则查询某个 s_k 的某个位置作为结束位置的值（单点查询，区间修改 max），这个点设为 v，如果有，就说明 v 的祖先有一个 u\in[l,r] 是 s_k 的子串。

也就是说，我们通过子树覆盖的方式解决了 s_i 是否出现的问题，用区间覆盖 max 的方式解决了区间限制问题。

如果你 s_i 出现在 s_k 中，令当前枚举到的 s_k 的结束位置，在 AC 自动机上对应的编号是 v，那么某个 s_i 的答案就是 v 子树里面标记的数量。由于你这个枚举结束过程相当于对每个结尾扫描线，所以总有一刻可以取到 s_i 对应节点和 s_{k,r} 对应节点重合的局面，因此不会漏掉答案。

现在问题是怎么快速搞到这些 u,v 和对应 v 的子串出现次数了。如果你直接每次询问都暴力遍历整个 AC 自动机的每个节点来查询，复杂度就很令人悲伤了。你考虑只保留有用的点，也就是建立一颗虚树，在这个虚树上保留所有 v（意义同上）的答案。

你需要做 \mathcal{O}(nB) 次单点查询（只保留了虚树上的点）， \mathcal{O}(n) 次区间覆盖，拿一个分块就可以做到 \mathcal{O}(1) 查询，\mathcal{O}(\sqrt{N}) 修改（N 是 AC 自动机节点个数）。

平衡复杂度取 B=\sqrt{N}，你粗浅的看一下，复杂度就是 \mathcal{O}((n+m)\sqrt{N}+m\log n) 的。但是我的代码拉完了跑的比较慢，所以要调一下 B。

:::success[代码有点长我折叠起来了]

# include <bits/stdc++.h>
# define pb push_back
using namespace std ;
constexpr int N = 1e5 + 5 , B = 1024 ; 
int n , m , cnt[5 * N] , id[N] , ans[N] ;
string s[N] ;  
struct QUERY { int l , r , k , id ; } Q[N] ; 
namespace ACAM {
int tr[26][5 * N] , fail[5 * N] ;
int tot ; 
vector < int > G[5 * N] ; 
void init () { memset ( tr , 0 , sizeof tr ) , memset ( fail , 0 , sizeof fail ) ; }
int insert ( string s ) { int u = 0 ; for ( auto & v : s ) ( ! tr[v - 'a'][u] ? tr[v - 'a'][u] = ++ tot : 0 ) , u = tr[v - 'a'][u] ; return u ; }
void getfail () {
    queue < int > q ; for ( int i = 0 ; i < 26 ; ++ i ) if ( tr[i][0] ) q.push ( tr[i][0] ) ; 
    while ( ! q.empty () ) {
        int now = q.front () ; q.pop () ; 
        for ( int i = 0 ; i < 26 ; ++ i )
            if ( tr[i][now] ) fail[tr[i][now]] = tr[i][fail[now]] , q.push ( tr[i][now] ) ; 
            else tr[i][now] = tr[i][fail[now]] ; 
    }
}
void buildfail () { for ( int i = 1 ; i <= tot ; ++ i ) G[fail[i]].pb ( i ) ;  }
} 
void dfs_count ( int u ) { for ( auto & v : ACAM :: G[u] ) dfs_count ( v ) , cnt[u] += cnt[v] ; }
vector < QUERY > q1[N] , q2[N] ;
int tr[N << 2] , trv[N] ; 
# define lid ( id << 1 )
# define rid ( id << 1 | 1 )
static inline void build ( int id , int l , int r ) {
    if ( l == r ) return tr[id] = trv[l] , void () ; 
    int mid = ( l + r ) >> 1 ; build ( lid , l , mid ) , build ( rid , mid + 1 , r ) ; 
    return tr[id] = max ( tr[lid] , tr[rid] ) , void () ; 
}
static inline int query ( int id , int pl , int pr , int l , int r ) {
    if ( pl >= l && pr <= r ) return tr[id] ; 
    int mid = ( pl + pr ) >> 1 , res = 0 ; 
    if ( l <= mid ) res = max ( res , query ( lid , pl , mid , l , r ) ) ; 
    if ( r > mid ) res = max ( res , query ( rid , mid + 1 , pr , l , r ) ) ; 
    return res ;  
}
# undef lid 
# undef rid 
namespace BLOCK {
int vl[5 * N] , tag[5 * N] , BB , SZ , st[N] , ed[N] , pos[5 * N] ;
void init ( int n ) { 
    for ( int i = 1 ; i <= n ; ++ i ) vl[i] = tag[i] = 0 ; 
    BB = sqrt ( n ) , SZ = n / BB ; 
    for ( int i = 1 ; i <= BB ; ++ i ) st[i] = (i - 1) * SZ + 1 , ed[i] = i * SZ ; ed[BB] = n ; 
    for ( int i = 1 ; i <= BB ; ++ i ) for ( int j = st[i] ; j <= ed[i] ; ++ j ) pos[j] = i ; 
}
void alter ( int l , int r , int pp ) { 
    if ( pos[l] == pos[r] ) { for ( int i = l ; i <= r ; ++ i ) vl[i] = max ( vl[i] , pp ) ; return ; }
    for ( int i = l ; i <= ed[pos[l]] ; ++ i ) vl[i] = max ( vl[i] , pp ) ; 
    for ( int i = st[pos[r]] ; i <= r ; ++ i ) vl[i] = max ( vl[i] , pp ) ; 
    for ( int i = pos[l] + 1 ; i <= pos[r] - 1 ; ++ i ) tag[i] = max ( tag[i] , pp ) ; 
}
int query ( int x ) { return max ( tag[pos[x]] , vl[x] ) ; }
} // 子树覆盖，单点查询
int sz[5 * N] , top[5 * N] , dfn[5 * N] , son[5 * N] , cur , dep[5 * N] , fa[5 * N] , rdfn[5 * N] ;
void dfs1 ( int u ) {
    sz[u] = 1 , dep[u] = dep[ACAM :: fail[u]] + 1 ; 
    fa[u] = ACAM :: fail[u] ; 
    for ( auto & v : ACAM :: G[u] ) {
        dfs1 ( v ) , sz[u] += sz[v] ; 
        if ( ! ~ son[u] || sz[v] > sz[son[u]] ) son[u] = v ; 
    }
}
static inline void dfs2 ( int u , int top ) {
    :: top[u] = top , dfn[u] = ++ cur , rdfn[cur] = u ; 
    if ( son[u] != -1 ) dfs2 ( son[u] , top ) ; 
    for ( auto & v : ACAM :: G[u] ) if ( v != son[u] ) dfs2 ( v , v ) ; 
    return ; 
}
static inline int LCA ( int u , int v ) {
    while ( top[u] != top[v] ) { if ( dep[top[u]] < dep[top[v]] ) swap ( u , v ) ; u = fa[top[u]] ; }
    if ( dep[u] < dep[v] ) return u ; return v ; 
}
int vtt[5 * N] , vtfa[5 * N] ; 
vector < pair < int , int > > vv[5 * N] ;  
vector < int > vtg[5 * N] ; 
static inline void dfs_vt ( int u ) { for ( auto & v : vtg[u] ) dfs_vt ( v ) , vtt[u] += vtt[v] ; return ; }
static inline void build_vt ( int now ) {
    vector < int > vtn , vt ;
    int u = 0 ; for ( auto & v : s[now] ) u = ACAM :: tr[v - 'a'][u] , vtn.pb ( u ) , ++ vtt[u] ; 
    sort ( vtn.begin () , vtn.end () , [&] ( int a , int b ) { return dfn[a] < dfn[b] ; } ) ; 
    vtn.erase ( unique ( vtn.begin () , vtn.end () ) , vtn.end () ) ;
    vt.pb ( 0 ) , vt.pb ( vtn[0] ) ; 
    for ( int i = 1 ; i < ( int ) vtn.size () ; ++ i ) vt.pb ( LCA ( vtn[i - 1] , vtn[i] ) ) , vt.pb ( vtn[i] ) ;
    sort ( vt.begin () , vt.end () , [&] ( int a , int b ) { return dfn[a] < dfn[b] ; } ) ; 
    vt.erase ( unique ( vt.begin () , vt.end () ) , vt.end () ) ; 
    for ( int i = 1 ; i < ( int ) vt.size () ; ++ i ) 
        vtfa[vt[i]] = LCA ( vt[i] , vt[i - 1] ) ,
        vtg[vtfa[vt[i]]].pb ( vt[i] ) ;
    for ( int i = ( int ) vt.size () - 1 ; i >= 1 ; -- i ) vtt[vtfa[vt[i]]] += vtt[vt[i]] ; 
    for ( int i = 1 ; i < ( int ) vt.size () ; ++ i ) vtg[vtfa[vt[i]]].clear () , vtfa[vt[i]] = 0 ; 
    for ( auto & u : vt ) vv[now].pb ( { u , vtt[u] } ) , vtt[u] = 0 ; 
}
signed main () {    
    ios::sync_with_stdio ( false ) , cin.tie ( 0 ) ; 
    cin >> n >> m ; ACAM :: init () ; 
    for ( int i = 1 ; i <= n ; ++ i ) cin >> s[i] , id[i] = ACAM :: insert ( s[i] ) ; 
    for ( int i = 1 ; i <= m ; ++ i ) {
        cin >> Q[i].l >> Q[i].r >> Q[i].k , Q[i].id = i ;
        if ( ( int ) s[Q[i].k].size () >= B ) q1[Q[i].k].pb ( Q[i] ) ; 
        else q2[Q[i].r].pb ( Q[i] ) ; 
    }
    ACAM :: getfail () ; 
    ACAM :: buildfail () ; 
    memset ( top , -1 , sizeof top ) ;   
    memset ( son , -1 , sizeof son ) ; 
    dfs1 ( 0 ) , dfs2 ( 0 , 0 ) ; 
    for ( int k = 1 ; k <= n ; ++ k ) {
        if ( q1[k].empty () ) continue ;            
        int u = 0 ; for ( auto & ch : s[k] ) u = ACAM :: tr[ch - 'a'][u] , ++ cnt[u] ;
        for ( int pos = ACAM :: tot + 1 ; pos >= 1 ; -- pos ) cnt[fa[rdfn[pos]]] += cnt[rdfn[pos]] ; 
        for ( int i = 1 ; i <= n ; ++ i ) trv[i] = cnt[id[i]] ;
        build ( 1 , 1 , n ) ; 
        for ( auto & qn : q1[k] ) ans[qn.id] = query ( 1 , 1 , n , qn.l , qn.r ) ; 
        memset ( cnt , 0 , (int) ( ACAM :: tot + 1 ) * sizeof ( int )  ) ; 
    }
    BLOCK :: init ( ACAM :: tot + 1 ) ; 
    for ( int i = 1 ; i <= n ; ++ i ) if ( ( int ) s[i].size () < B ) build_vt ( i ) ;
    int idn = 1 ;
    for ( int r = 1 ; r <= n ; ++ r ) {
        while ( idn <= r ) BLOCK :: alter ( dfn[id[idn]] , dfn[id[idn]] + sz[id[idn]] - 1 , idn ) , ++ idn ; 
        for ( auto & v : q2[r] ) { 
            int mx = 0 ; 
            for ( auto & x : vv[v.k] )
                if ( BLOCK :: query ( dfn[x.first] ) >= v.l ) mx = max ( mx , x.second ) ; 
            ans[v.id] = mx ; 
        }
    }
    for ( int i = 1 ; i <= m ; ++ i ) cout << ans[i] << "\n" ; return 0 ; 
}
// s_k < B，吧s_i<B的插入一下虚树，然后就变成查询一个节点的最大值，区间的限制：r通过扫描线保证
// 一个s_i在fail树上面，如果能影响到一个查询，结构应该是怎么样的？
// A:这个查询一定是通过跳fail（父亲）来走到当前的s_i，所以对于每个插入的s_i标记一下它的子树就行
// 查询的时候就看你怎么搞到某个s_k的k的所有endpos和对应的val，也就是出现次数
// 然后fail树上有祖先后代关系则说明s_i可以通过跳fail来位于s_k内，换句话说s_i的出现次数就是val_{sk某个endpos的那个u}

:::