笨蛋花的小窝qwq

笨蛋花的小窝qwq

“我要再和生活死磕几年。要么我就毁灭,要么我就注定铸就辉煌。如果有一天,你发现我在平庸面前低了头,请向我开炮。”

题解 P5840 【[COCI2015] Divljak】

posted on 2019-12-20 10:10:28 | under 题解 |

首先给烈士搬题人上香

大概是考虑,反正是匹配问题——那么是对着 $\rm T$ 建自动机呢,还是对 $\rm \{S_n\}$ 建。 考虑 AC 自动机更适合做这种匹配题,于是大概想到要拿 AC 自动机做;考虑如果对着 $\rm T$ 建自动机,树的形态会变,$\rm S$ 的信息需要动态维护,并不很好做,于是考虑对 $\rm S$ 建自动机 $\rm AC_s$。

考虑这样做,就需要在已经建好的自动机上,对于每个新加进来的 $P$ 计算贡献。那么会被 $P$ 包含的字符串,一定是 $P$ 在 $\rm AC_s$ 里匹配的 $endpos$ 到根的路径上每个点,到根的链上的点集并。暴力是 $n^2$ 的,考虑如何快速计算这个贡献,发现能做到最快的,也就是通过维护 dfs 序的方式求出点集并。对于每一个这样的链的并打一个标记。询问的时候只需要回答一下子树内有多少个点被打了不同的标记。

发现「维护树链标记」+「子树求和」,最快速的方法是维护差分。同时由于是动态的,可以想到用线段树或者 BIT 快速维护。

考虑修改如何进行。发现为了保证 $\and$ 形态的链只会被计数一次,需要在 $lca$ 处差分。此处需要注意的是,要对 $dfs$ 序排序之后,再逐个差分,方法是 $(i,+1),(i+1,+1),(lca_{i,i+1},-1)$ 。

想了半天才大约明白为什么要按 dfs 序排一遍序。大概是如果不按 dfs 序的顺序枚举,可能会出现某个子树未被成功打上标记的情况。

最终复杂度是 $O(\rm |S|\log |S|)$ 的,跑的不是很快。

哦,对,_end是关键字,千万别忘了。

#define Sigma 27
#define il inline
#define MAXN 2000010

using namespace std ;

char S[MAXN] ;
int T, M, N, L[MAXN] ;
struct Edge{
    int to, next ;
    #define to(k) E[k].to
    #define next(k) E[k].next
}E[MAXN] ; int head[MAXN], base[MAXN], cnt, tot ;
int _ed[MAXN], dfn[MAXN], rgl[MAXN], rgr[MAXN], tp ;
int sz[MAXN], dep[MAXN], fa[MAXN], top[MAXN], son[MAXN], val[MAXN] ;

void add(int u, int v){
    E[++ cnt].to = v, E[cnt].next = head[u], head[u] = cnt ;
}
void dfs(int u){
    sz[u] = 1, dep[u] = dep[fa[u]] + 1 ;
    for (int k = head[u] ; k ; k = next(k)){
        fa[to(k)] = u, dfs(to(k)), sz[u] += sz[to(k)] ;
        if (!son[u] || sz[to(k)] > sz[son[u]]) son[u] = to(k) ;
    }
}
void dfs2(int u, int tp){
    top[u] = tp,
    dfn[u] = rgl[u] = ++ tot ;
    if (son[u]) dfs2(son[u], tp) ;
    for (int k = head[u] ; k ; k = next(k))
        if (to(k) != son[u]) dfs2(to(k), to(k)) ;
    rgr[u] = tot ;
}
il bool comp(int x, int y){ return dfn[x] < dfn[y] ; }
int lca(int u, int v){
    while (top[u] != top[v]){
        if (dep[top[u]] >= dep[top[v]]) u = fa[top[u]] ;
        else v = fa[top[v]] ;
    }
    return dep[u] < dep[v] ? u : v ;
}

void _up(int rt){
    val[rt] = val[rt << 1] + val[rt << 1 | 1] ;
}
void update(int rt, int l, int r, int p, int v){
    if (l == r)
        return val[rt] += v, void() ;
    int mid = (l + r) >> 1 ;
    if (mid >= p)
        update(rt << 1, l, mid, p, v) ;
    else update(rt << 1 | 1, mid + 1, r, p, v) ;
    _up(rt) ;
}
int query(int rt, int l, int r, int pl, int pr){
    if (pl > pr) return 0 ; 
    if (l >= pl && pr >= r) return val[rt] ;
    int mid = (l + r) >> 1, res = 0 ;
    if (pl <= mid) res += query(rt << 1, l, mid, pl, pr) ;
    if (pr > mid) res += query(rt << 1 | 1, mid + 1, r, pl, pr) ;
    return res ;
}
struct ACAM{
    queue <int> q ;
    int _size, fail[MAXN] ;
    int trie[MAXN][Sigma] ;
    void insert(char *s, int n){
        int rt = 0, x ;
        for (int i = 1 ; i <= L[n] ; ++ i){
            x = s[i] - 'a' ;
            if (!trie[rt][x])
                trie[rt][x] = ++ _size ;
            rt = trie[rt][x] ;
        }
        _ed[n] = rt ;
    }
    void build(){
        for (int i = 0 ; i < Sigma ; ++ i)
            if (trie[0][i]) q.push(trie[0][i]) ;
        while (!q.empty()){
            int n = q.front() ; add(fail[n], n), q.pop() ;
            for (int i = 0 ; i < 26 ; ++ i){
                if (!trie[n][i]) trie[n][i] = trie[fail[n]][i] ;
                else fail[trie[n][i]] = trie[fail[n]][i], q.push(trie[n][i]) ;
            }
        }
    }
    void solve(char *S){
        int x, rt = 0 ; tp = 0 ;
        for (int i = 1 ; i <= N ; ++ i)
            x = S[i] - 'a', rt = trie[rt][x], base[++ tp] = rt ;
        sort(base + 1, base + tp + 1, comp),
        tp = unique(base + 1, base + tp + 1) - base - 1 ;
        for (int i = 1 ; i <= tp ; ++ i){
            update(1, 1, tot, dfn[base[i]], 1) ;
            if (i > 1) update(1, 1, tot, dfn[lca(base[i], base[i - 1])], -1) ;
        }
    }
}AC ;

int qr(){
    int r = 0 ; char c = getchar() ;
    while (!isdigit(c)) c = getchar() ;
    while (isdigit(c)) r = (r << 1) + (r << 3) + c - 48, c = getchar() ;
    return r ;
}
int main(){
    // freopen("1.in", "r", stdin) ;
    // freopen("1.ans", "w", stdout) ;
    cin >> T ; int m, q ;
    for (int i = 1 ; i <= T ; ++ i)
        scanf("%s", S + 1), L[i] = strlen(S + 1), AC.insert(S, i) ;
    AC.build() ; cin >> M ; dfs(0), dfs2(0, 0) ;
//    for (int i = 1 ; i <= T ; ++ i) cout << rgl[i] << " " << rgr[i] << endl ;
    while (M --){
        m = qr() ;
        if (m == 1) scanf("%s", S + 1), N = strlen(S + 1), AC.solve(S) ;
        else q = qr(),
            printf("%d\n", query(1, 1, tot, 1, rgr[_ed[q]]) - query(1, 1, tot, 1, rgl[_ed[q]] - 1)) ;
    }
    return 0 ; 
}

吐槽

  • 为啥lxl常数这么小啊(

  • _end这东西一调一上午啊qaq