题目链接：LOJ 2033

魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。例如可以将魔咒字符 $1$、$2$ 拼凑起来形成一个魔咒串 $[1, 2]$。

一个魔咒串 $S$ 的非空子串被称为魔咒串 $S$ 的生成魔咒。

例如 $S = [1, 2, 1]$ 时，它的生成魔咒有 $[1]$、$[2]$、$[1, 2]$、$[2, 1]$、$[1, 2, 1]$ 五种。$S = [1, 1, 1]$ 时，它的生成魔咒有 $[1]$、$[1, 1]$、$[1, 1, 1]$ 三种。

最初 $S$ 为空串。共进行 $n$ 次操作，每次操作是在 $S$ 的结尾加入一个魔咒字符。每次操作后都需要求出，当前的魔咒串 $S$ 共有多少种生成魔咒。

数据范围：$1 \le n \le 10 ^ 5$，$1 \le \Sigma \le 10 ^ 9$。

Solution

我们对字符串 $S$ 建立后缀自动机，由于 $\text{SAM}$ 是在线的，那么每次插入一个字符后，产生的贡献就是节点 $last$ 的贡献。而这个贡献就是其父节点无法表示出的子串数量，即 $len(last) - len(link(last))$。

因为字符集大小为 $10 ^ 9$，因此需要使用 $\text{map}$ 维护转移。

时间复杂度：$\mathcal O(n \log \Sigma)​$。

Code

#include <cstdio>
#include <map>

const int N = 1e5 + 5;

int n;

template <int N>
struct SAM {
    int n, lst;
    struct State {
        int len, lnk;
        std::map<int, int> nxt;
    } st[N << 1];
    SAM() {
        st[n = lst = 0].lnk = -1;
    }
    void extend(int x) {
        int cur = ++n;
        st[cur].len = st[lst].len + 1;
        int p = lst;
        for (; ~p && !st[p].nxt.count(x); p = st[p].lnk) {
            st[p].nxt[x] = cur;
        }
        if (p == -1) {
            st[cur].lnk = 0;
        } else {
            int q = st[p].nxt[x];
            if (st[q].len == st[p].len + 1) {
                st[cur].lnk = q;
            } else {
                int clone = ++n;
                st[clone].len = st[p].len + 1;
                st[clone].lnk = st[q].lnk;
                st[clone].nxt = st[q].nxt;
                for (; ~p && st[p].nxt[x] == q; p = st[p].lnk) {
                    st[p].nxt[x] = clone;
                }
                st[cur].lnk = st[q].lnk = clone;
            }
        }
        lst = cur;
    }
};

SAM<N> S;

int main() {
    scanf("%d", &n);
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        int x;
        scanf("%d", &x);
        S.extend(x);
        int u = S.lst, v = S.st[u].lnk;
        ans += S.st[u].len - S.st[v].len;
        printf("%lld\n", ans);
    }
    return 0;
}