P4248 [AHOI2013]差异

P4248 [AHOI2013]差异

Algorithm I 后缀数组

注意到 $\sum _ {1 \le i < j \le n} i + j$ 为定值：
$$
\begin {aligned}
& \sum _ {i \le i < j \le n} i + j \\
= & \sum _ {i = 1} ^ n \sum _ {j = i + 1} ^ n i + j \\
= & \sum _ {i = 1} ^ n (n - i)i + \frac {(i + 1 + n) (n - i)} 2 \\
= & \sum _ {i = 1} ^ n \frac {n ^ 2 + n + 2i n - 3i ^ 2 - i} 2 \\
= & \frac {n ^ 3 + n ^ 2 + 2n \frac {n(n + 1)} 2 - 3\frac {n (n + 1) (2n + 1)} 6 - \frac {n (n + 1)} 2} 2 \\
= & \frac {n ^ 3 - n} 2
\end {aligned}
$$
需要求任意两个后缀 $lcp$ 之和。考虑求出 $height$ 后，即任意两个区间的最小值的和，可以用单调栈做。

注意细节，最后一定要把栈内答案加上。

查看代码

#include <cstdio>
#include <cstring>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    if (flag) x = ~x + 1;
}
template <class Type, class ...rest>
void read(Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write(Type x)
{
    if (x < 0) putchar('-'), x = ~x + 1;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
typedef long long LL;
const int N = 1e6 + 10;
char str[N];
int top, stk[N];
int n, m, sa[N], rnk[N], ht[N], x[N], y[N], c[N];
void bucsort ()
{
    for (int i = 1; i <= m; ++i) c[i] = 0;
    for (int i = 1; i <= n; ++i) ++c[x[i]];
    for (int i = 2; i <= m; ++i) c[i] += c[i - 1];
    for (int i = n; i; i--) sa[c[x[y[i]]]--] = y[i];
}
void init ()
{
    for (int i = 1; i <= n; ++i)
        x[i] = str[i] - 'a' + 1, y[i] = i, sa[i] = 0;
    bucsort();
    for (int k = 1; k <= n; k <<= 1)
    {
        int cnt = 0;
        for (int i = n - k + 1; i <= n; ++i) y[++cnt] = i;
        for (int i = 1; i <= n; ++i)
            if (sa[i] > k) y[++cnt] = sa[i] - k;
        bucsort();
        for (int i = 1; i <= n; ++i) y[i] = x[i];
        x[sa[1]] = cnt = 1;
        for (int i = 2; i <= n; ++i)
            x[sa[i]] = cnt += (y[sa[i]] ^ y[sa[i - 1]] || y[sa[i] + k] ^ y[sa[i - 1] + k]);
        if ((m = cnt) == n) break;
    }
    for (int i = 1; i <= n; ++i) rnk[sa[i]] = i;
    for (int i = 1, k = 0; i <= n; ++i)
    {
        int j = sa[rnk[i] - 1];
        if (k) --k;
        while (str[i + k] == str[j + k]) ++k;
        ht[rnk[i]] = k;
    }
}
int main ()
{
    scanf("%s", str + 1);
    n = strlen(str + 1), m = 26;
    init();
    LL res = (LL)(n - 1) * n / 2 * (n + 1);
    stk[0] = 1;
    for (int i = 2; i <= n; ++i)
    {
        while (top && ht[stk[top]] >= ht[i])
            res -= 2ll * ht[stk[top]] * (i - stk[top]) * (stk[top] - stk[top - 1]), --top;
        stk[++top] = i;
    }
    while (top)
        res -= 2ll * ht[stk[top]] * (n + 1 - stk[top]) * (stk[top] - stk[top - 1]), --top;
    write(res);
    return 0;
}

后缀树

注意到形式和树上差分很相似，发现答案即后缀树上后缀距离之和。建出后缀树，将反串建 SAM 即可。一个点上可能是多个字符，字符数有 $len _ i - len _ p$ 个，即边长。记录子树中有多少个点，对于每条边统计答案即可。

查看代码

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
template <class Type>
void read (Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type, class ...rest>
void read (Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write (Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar('0' + x % 10);
}
typedef long long LL;
const int N = 1e6 + 10;
char str[N];
vector <int> g[N];
LL ans;
int n, last = 1, cnt = 1, sz[N];
struct Node { int p, len, nxt[26]; } tr[N];
void extend (int c)
{
    int p = last, np = ++cnt;
    sz[cnt] = 1;
    tr[np].len = tr[p].len + 1;
    for (; p && !tr[p].nxt[c]; p = tr[p].p) tr[p].nxt[c] = np;
    last = np;
    if (!p) return void(tr[np].p = 1);
    int q = tr[p].nxt[c];
    if (tr[q].len == tr[p].len + 1) return void(tr[np].p = q);
    int nq = ++cnt;
    tr[nq] = tr[q], tr[nq].len = tr[p].len + 1;
    tr[q].p = tr[np].p = nq;
    for (; p && tr[p].nxt[c] == q; p = tr[p].p) tr[p].nxt[c] = nq;
}
void dfs (int u)
{
    for (int v : g[u])
    {
        dfs(v);
        ans += (LL)(n - sz[v]) * sz[v] * (tr[v].len - tr[u].len);
        sz[u] += sz[v];
    }
}
int main ()
{
    scanf("%s", str);
    n = strlen(str);
    for (int i = n - 1; ~i; --i) extend(str[i] - 'a');
    for (int i = 2; i <= cnt; ++i) g[tr[i].p].push_back(i);
    dfs(1);
    write(ans);
    return 0;
}