题目描述

魔咒串由许多魔咒字符组成，魔咒字符可以用数字表示。

例如可以将魔咒字符 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 共有多少种生成魔咒。

输入描述

第一行一个整数 n。

第二行 n 个数，第 i 个数表示第 i 次操作加入的魔咒字符。

输出描述

$1≤n≤10^5$,
用来表示魔咒字符的数字 x 满足 $1≤x≤10^9$

样例

输入
7
1 2 3 3 3 1 2

输出 

1
3
6
9
12
17
22

题解

思路

后缀自动机

SAM求不同子串数量，只需要对每个节点，求 $len(i) - len(link(i))$ 求和即可，
所以我们可以每次extend一个字符的时候，让$ans += len(last) - len(link(lase))$ 即可

代码

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const size_t N = 2e5 + 10;

struct node {
    int fa, len;
    unordered_map<int, int> ch;
} sam[N];

int tot = 1, last = 1;

ll ans;

void extend(int c) {
    int p = last, np = last = ++tot;
    sam[np].len = sam[p].len + 1;
    for (; p && !sam[p].ch[c]; p = sam[p].fa) sam[p].ch[c] = np;
    if (!p) sam[np].fa = 1;
    else {
        int q = sam[p].ch[c];
        if (sam[q].len == sam[p].len + 1) sam[np].fa = q;
        else {
            int nq = ++tot;
            sam[nq] = sam[q], sam[nq].len = sam[p].len + 1;
            sam[q].fa = sam[np].fa = nq;
            for (; p && sam[p].ch[c] == q; p = sam[p].fa) sam[p].ch[c] = nq;
        }
    }
    ans += sam[last].len - sam[sam[last].fa].len;
}

int main() {
    int n;
    cin >> n;
    int c;
    for (int i = 0; i < n; i++) {
        scanf("%d", &c);
        extend(c);
        printf("%lld\n", ans);
    }
    return 0;
}