题目戳我= ̄ω ̄=

首先添加一个字符以后多出来的子串都是包含当前字符的后缀,我们就是要把它们的 $f$给加上去

假设添加当前字符 $c$前的某个后缀为 $x – c$,添加完 $c$之后就变成了 $x$,那么 $f(x – c)$那一部分是没变的,也就是说 $f(x) – f(x – c)$等于新添加的字符深度,因此我们只要统计当前字符的贡献就行了

可以发现一个点在 fail 树中的深度就等于以它结尾的后缀能匹配多少前缀,由于这题是要统计每个后缀中这个点的深度,因此就把 “前缀” 这个限定去掉,问题就是以它结尾的后缀能匹配多少子串,这个用后缀自动机就能做了

一边插入后缀自动机,一边统计等价类大小以及 endpos 集合大小

具体来说,插入某个点后,它在后缀自动机中的 fail 树上的祖先们的 endpos 集合大小都会+1,这个事情用 lct 可以维护,也可以离线然后树链剖分

不用担心离线的时候先把 SAM 建出来会导致点数变多出错之类的,因为 SAM 添加节点后只会细分 SAM,而不会导致之前的信息丢失,只要建的时候不添加 endpos 之类的信息,只是把 SAM 的结构建出来是不会出错的

复杂度 $O(n \log _ 2 ^ 2 n)$

偷懒写了随机剖分_(:зゝ∠)_

(然而这题实际上暴力跑的最快)

另外一开始被取模加法坑飞了,一开始写的是 #define pls(a, b) ((a) + (b) < MOD ? (a) + (b) : (a) + (b) - MOD),define 会原封不动地把你填进去的参数照抄三遍,就算是函数也会照抄三遍,这导致每次会调用两边函数,放到线段树里复杂度就不知道高了多少。。。

以后还是不用 define 了吧

代码:

#include <bits/stdc++.h>

#define NS (100005)
#define MOD (1000000007)
#define LS(a) ((a) << 1)
#define RS(a) ((a) << 1 | 1)

using namespace std;

inline int pls(int a, int b)
{
    return a + b < MOD ? a + b : a + b - MOD;
}

inline int mul(int a, int b) { return 1ll * a * b % MOD; }

template<typename _Tp> inline void IN(_Tp &dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, lst[NS], D[NS << 1], V[NS << 3], S[NS << 3], tag[NS << 3];

char s[NS];

void build(int l, int r, int a)
{
    if (l == r) { V[a] = D[l]; return; }
    int mid = (l + r) >> 1;
    build(l, mid, LS(a)), build(mid + 1, r, RS(a));
    V[a] = pls(V[LS(a)], V[RS(a)]);
}

void pup(int a) { S[a] = pls(S[LS(a)], S[RS(a)]); }

void pdown(int a)
{
    if (!tag[a]) return;
    int l = LS(a), r = RS(a);
    S[l] = pls(S[l], mul(tag[a], V[l]));
    S[r] = pls(S[r], mul(tag[a], V[r]));
    tag[l] = pls(tag[l], tag[a]);
    tag[r] = pls(tag[r], tag[a]);
    tag[a] = 0;
}

int _query(int l, int r, int L, int R, int a)
{
    if (l <= L && R <= r) return S[a];
    pdown(a);
    int Mid = (L + R) >> 1, res = 0;
    if (l <= Mid) res = _query(l, r, L, Mid, LS(a));
    if (r > Mid) res = pls(res, _query(l, r, Mid + 1, R, RS(a)));
    return res;
}

void _add(int l, int r, int L, int R, int a)
{
    if (l <= L && R <= r) { S[a] = pls(S[a], V[a]), tag[a]++; return; }
    pdown(a);
    int Mid = (L + R) >> 1;
    if (l <= Mid) _add(l, r, L, Mid, LS(a));
    if (r > Mid) _add(l, r, Mid + 1, R, RS(a));
    pup(a);
}

struct SAM
{
    struct N
    {
        int nxt[26], l, f;
        int & operator [] (const char c) { return nxt[c - 'a']; }
    } e[NS << 1];
    int lst, sz;
    SAM() { lst = sz = 1; }
    void insert(char c)
    {
        int a = ++sz, p = lst;
        e[a].l = e[p].l + 1, lst = a;
        while (p && !e[p][c]) e[p][c] = a, p = e[p].f;
        if (!p) { e[a].f = 1; return; }
        int q = e[p][c];
        if (e[q].l == e[p].l + 1) { e[a].f = q; return; }
        int nq = ++sz;
        e[nq] = e[q], e[nq].l = e[p].l + 1, e[a].f = e[q].f = nq;
        while (e[p][c] == q) e[p][c] = nq, p = e[p].f;
    }
    vector<int> g[NS << 1];
    int top[NS << 1], id[NS << 1], dfn;
    void tree() { for (int i = 1; i <= sz; i += 1) g[e[i].f].push_back(i); }
    void dfs(int a)
    {
        if (!top[a]) top[a] = a;
        id[a] = ++dfn, D[dfn] = e[a].l - e[e[a].f].l;
        if (g[a].empty()) return;
        int nxt = g[a][rand() % g[a].size()];
        top[nxt] = top[a], dfs(nxt);
        for (int i = 0; i < g[a].size(); i += 1)
            if (g[a][i] != nxt) dfs(g[a][i]);
    }
    int query(int a)
    {
        int res = 0;
        while (a)
        {
            res = pls(res, _query(id[top[a]], id[a], 1, sz, 1));
            a = e[top[a]].f;
        }
        return res;
    }
    void add(int a)
    {
        while (a)
        {
            _add(id[top[a]], id[a], 1, sz, 1);
            a = e[top[a]].f;
        }
    }
} sam;

int main(int argc, char const* argv[])
{
    srand(19260817), IN(n), scanf("%s", s + 1);
    for (int i = 1; i <= n; i += 1) sam.insert(s[i]), lst[i] = sam.lst;
    sam.tree(), sam.dfs(1), build(1, sam.sz, 1);
    for (int i = 1, ans = 0, dt = 0; i <= n; i += 1)
    {
        dt = pls(dt, sam.query(lst[i])), ans = pls(ans, dt);
        sam.add(lst[i]), printf("%d\n", ans);
    }
    return 0;
}
分类: 文章

Remmina

No puzzle that couldn't be solved.

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注