后缀数组笔记

为什么 xht 注意力这么惊人啊。

从前往后加入字符，对每个前缀求有多少本质不同子串。
并不难想到后缀数组，但是对每个前缀都求一次肯定是爆表的，因为每次在后面加一个字符改动的 $ht$ 数组是 $O(n)$ 级别。
然而一个很巧妙的做法是把字符串倒序，这样每次在最前面加入一个字符。
这样不会改变答案，而且在最前面加入一个字符相当于插入一个 $ht$！

注意其实本质不同子串数可以表示为 $\sum\limits_{i=1}^{n} n - sa_i + 1 - ht_i$，可以通过此公式算出任意一个前缀的答案。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, a[N], b[N], m;

int x[N], y[N], cnt[N], sa[N], rk[N], ht[N];
void init_SA() {
    int v = m;
    for (int i = 0; i <= v; i++) cnt[i] = 0;
    for (int i = 1; i <= n; i++) cnt[x[i] = a[i]]++;
    for (int i = 1; i <= v; i++) cnt[i] += cnt[i - 1];
    for (int i = n; i >= 1; i--) sa[ cnt[x[i]]-- ] = i;
    for (int len = 1; ; len <<= 1) {
        int tot = 0;
        for (int i = n - len + 1; i <= n; i++) y[++tot] = i;
        for (int i = 1; i <= n; i++)
            if (sa[i] > len) y[++tot] = sa[i] - len;

        for (int i = 0; i <= v; i++) cnt[i] = 0;
        for (int i = 1; i <= n; i++) cnt[x[i]]++;
        for (int i = 1; i <= v; i++) cnt[i] += cnt[i - 1];
        for (int i = n; i >= 1; i--) sa[ cnt[x[y[i]]]-- ] = y[i], y[i] = 0;

        swap(x, y), tot = 0;
        for (int i = 1; i <= n; i++) {
            if (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + len] == y[sa[i - 1] + len]) x[sa[i]] = tot;
            else x[sa[i]] = ++tot;
        }
        v = tot;
        if (v == n) break;
    }
}

void init_height() {
    for (int i = 1; i <= n; i++) rk[sa[i]] = i;
    for (int i = 1, j = 0, now = 0; i <= n; i++) {
        if (rk[i] == 1) { ht[rk[i]] = 0; continue; }
        j = sa[rk[i] - 1], now = max(now - 1, 0);
        while (i + now <= n && j + now <= n && a[i + now] == a[j + now]) now++;
        ht[rk[i]] = now;
    }
}

long long ans = 0;
set<int> s;

int lg[N], mn[N][19];
void init_ST() {
    lg[1] = 0; for (int i = 2; i <= n; i++) lg[i] = lg[i >> 1] + 1;
    for (int i = 1; i <= n; i++) mn[i][0] = ht[i];
    for (int i = 1; i <= 18; i++)
        for (int j = 1; j + (1 << i) - 1 <= n; j++)
            mn[j][i] = min(mn[j][i - 1], mn[j + (1 << i - 1)][i - 1]);
}
int query(int l, int r) {
    int len = lg[r - l + 1];
    return min(mn[l][len], mn[r - (1 << len) + 1][len]);
}
int LCP(int a, int b) { return query(a + 1, b); }

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), b[i] = a[i];
    sort(b + 1, b + 1 + n), m = unique(b + 1, b + 1 + n) - b - 1;
    for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + 1 + m, a[i]) - b;
    reverse(a + 1, a + 1 + n);
    init_SA(), init_height();
    init_ST();

    for (int i = n; i >= 1; i--) {
        s.insert(rk[i]);
        auto t1 = s.find(rk[i]), t2 = s.find(rk[i]); t2++;
        bool f = 1;
        if (t1 != s.begin()) t1--, ans -= LCP((*t1), rk[i]);
        else f = 0;
        if (t2 != s.end()) ans -= LCP(rk[i], (*t2));
        else f = 0;
        if (f) ans += LCP((*t1), (*t2));
        ans += n - i + 1;
        printf("%lld\n", ans);
    }
    return 0;
}