洛谷P4248 [AHOI2013] 差异题解

题目链接：P4248 [AHOI2013] 差异

题意：

给定一个长度为 \(n\) 的字符串 \(S\)，令 \(T_i\) 表示它从第 \(i\) 个字符开始的后缀。求 \[ \displaystyle \sum_{1\le i<j\le n}\operatorname{len}(T_i)+\operatorname{len}(T_j)-2\times\operatorname{lcp}(T_i,T_j) \] 其中，\(\text{len}(a)\) 表示字符串 \(a\) 的长度，\(\text{lcp}(a,b)\) 表示字符串 \(a\) 和字符串 \(b\) 的最长公共前缀。

输入格式：

一行，一个字符串 \(S\)。

输出格式：

一行，一个整数，表示所求值。

数据范围：

对于 \(100\%\) 的数据，保证 \(2\le n\le 5\times 10^5\)，且 \(S\) 中均为小写字母。

\(\mathcal{Part}\ 1\)

首先化简式子 \[ \begin{aligned} \mathrm{Ans} &= \sum_{1 \leq i<j \leq n} (i+j)-2 \times \sum_{1 \leq i<j \leq n} \operatorname{lcp}\left(T_i, T_j\right) \\[8pt] &=\frac{n(n-1)(n+1)}{2}-2 \times \sum_{1 \leq i<j \leq n} \operatorname{lcp}\left(T_i, T_j\right) \end{aligned} \] 考虑对字符串构建后缀数组，并构建 height 数组。

\(\mathcal{Part}\ 2\)

下面来介绍一下什么是 height 数组，知道的可以直接跳过了。

定义 \(\operatorname{LCP}(i,j)=\operatorname{lcp}(T_{\texttt{sa[i]}}, T_{\texttt{sa[j]}})\) ，即排名第 \(i\) 的后缀和排名第 \(j\) 的后缀的最长公共前缀的长度。

定义 \(\texttt{height[i]} = \operatorname{LCP}(i-1,\,i)\) ，即排名为 \(i(i > 1)\) 的后缀与它前一名的后缀的最长公共前缀的长度。

记 \[ h_i=\texttt{height[rk[i]]} = \operatorname{LCP}(\texttt{rk[i]}-1,\,\texttt{rk[i]}) = \operatorname{lcp}(T_\texttt{sa[rk[i]-1]},\,T_i) \] 即后缀 \(T_i\) 与排序后在它前一名的后缀的最长公共前缀的长度。

定理1： \[ \mathrm{LCP}(i,j) = \min_{i+1 \le k \le j}\{\mathrm{LCP}(k-1,\,k)\}\quad (i < j) \]

证明请参考这个。

推论1： \[ \operatorname{LCP}(i,k) = \min\{\operatorname{LCP}(i,j),\,\operatorname{LCP}(j,k)\}\quad(i < j < k) \] 证明显然。注意这里对任意合法的 \(j\) 都成立。

推论2： \[ \operatorname{LCP}(i,k) \le \operatorname{LCP}(j,k)\quad(i \le j < k) \] 证明显然（由推论1）。

推论3： \[ \begin{aligned} \operatorname{LCP}(i,j) &= \min_{i + 1 \le k \le j}\{ \mathtt{height[k]}\} \end{aligned} \] 证明显然（代入定理1）。

这个推论非常重要，当 height 数组固定时可以转化为 RMQ 问题。

定理2： \[ h_i \ge h_{i-1}-1 \]

或者说 \[ \texttt{height[rk[i]]} \ge \texttt{height[rk[i-1]]}-1 \] 证明如下：

首先 \(h_{i-1} \le 1\) 时显然成立，以下假设 \(h_{i-1} > 1\) 。

设 \(k=\texttt{sa[rk[i-1]-1]}\) ，即 \(T_{i-1}\) 排序后在它前一位的是 \(T_k\) 。

根据定义 \(h_{i-1} = \operatorname{LCP}(\texttt{rk[k]},\texttt{rk[i-1]}) = \operatorname{lcp}(T_k,T_{i-1})\) 就是 \(T_{i-1}\) 和 \(T_{k}\) 的最长公共前缀的长度。

因为 \(h_{i-1} > 1\) ，所以 \(T_{k+1}\) 会排在 \(T_i\) 前面，那么根据定理1的推论2和 \(k\) 的定义，有 \[ \operatorname{LCP}(\texttt{rk[k+1]},\texttt{rk[i]})=\operatorname{lcp}(T_{k+1},T_{i})=h_{i-1}-1 \le \operatorname{LCP}(\texttt{rk[i]}-1,~\texttt{rk[i]})=h_i \] 即 \(h_i \ge h_{i-1}-1\) 。\(\square\)

由定理2，我们可以线性构建 height 数组了，如下

void getlcp(const int n)
{
    int k = 0;
    for(int i = 1; i <= n; height[rk[i]] = k, i++)
    {
        const int j = sa[rk[i] - 1]; if(k) --k;
        while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) ++k;
    }
}

\(\mathcal{Part}\ 3\)

本题难点在于怎么计算下面这坨东西 \[ \sum_{1 \leq i<j \leq n} \operatorname{lcp}\left(T_i, T_j\right) \] 显然它等于 \[ \begin{aligned} \sum_{1 \leq i<j \leq n} \operatorname{lcp}\left(T_{\texttt{sa[i]}}, T_{\texttt{sa[j]}}\right) &=\sum_{1 \leq i<j \leq n} \operatorname{LCP}\left(i,j\right) \\[6pt]&= \sum_{1 \leq i<j \leq n}\left( \min_{i+1\le k \le j}\{\texttt{height[k]}\}\right) \end{aligned} \] 这个求和属于老套路了，我们考察每个 \(\texttt{height[k]}\) 的贡献。

可以发现，对于 \(2 \le k \le n\) ，\(\texttt{height[k]}\) 的贡献为 \[ \texttt{height[k]} \times(k-l_k)\times(r_k-k) \] 其中 \(l_k\) 和 \(r_k\) 分别表示排名小于/大于 \(k\) 的第一个 height 值小于等于 \(\texttt{height[k]}\) 的位置。

换句话说，对于 \(i \in [l_k,k),~j \in [k,r_k)\) 的组合 \((i,j)\) ，他们的值都是 \(\texttt{height[k]}\) 。

这个可以用单调栈维护：

初始栈里有一个 \(1\) ，表示位置 \(1\) 。
依次考虑每个 \(i~(2 \le i \le n)\) ，如果 \(\texttt{height[i]}\) 小于栈顶的 height 值，就一直弹出栈顶
这些弹出的元素，他们的 \(r\) 就是 \(i\) 。弹到不能弹了，栈顶元素就是 \(l_i\)，然后加入 \(i\) 。
最后如果栈里还有元素，就一直弹，弹出的元素的 \(r\) 都是 \(n+1\) ，即右侧没有比它小的。

upd. 其实这个东西类似于笛卡尔树的线性构建。

时间复杂度 \(\mathcal{O}(n \log n)\) ，复杂度瓶颈是建后缀数组，其他都是线性的。

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define N ((int)(5e5 + 15))
#define check(i, w) (tmp[sa[i]] == tmp[sa[i - 1]] && tmp[sa[i] + w] == tmp[sa[i - 1] + w])

char s[N];
int top, stk[N], sa[N], rk[N * 2], tmp[N * 2], height[N], cnt[N], l[N], r[N];
void sort(const int n, const int m, int w)
{
    memset(cnt, 0, sizeof(int) * (m + 5));
    for(int i = 1; i <= n; i++) tmp[i] = sa[i];
    for(int i = 1; i <= n; i++) ++cnt[rk[tmp[i] + w]];
    for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
    for(int i = n; i; i--) sa[cnt[rk[tmp[i] + w]]--] = tmp[i];
}
void getlcp(const int n)
{
    int k = 0;
    for(int i = 1; i <= n; height[rk[i]] = k, i++)
    {
        const int j = sa[rk[i] - 1]; if(k) --k;
        while(i + k <= n && j + k <= n && s[i + k] == s[j + k]) ++k;
    }
}
void init(const int n)
{
    const int m = max(n, 233);
    for(int i = 1; i <= n; i++) { sa[i] = i, rk[i] = s[i]; }
    for(int w = 1; w < n; w *= 2)
    {
        sort(n, m, w); sort(n, m, 0);
        for(int i = 1; i <= n; i++) tmp[i] = rk[i];
        for(int i = 1, p = 0; i <= n; i++)
            if(check(i, w)) rk[sa[i]] = p; else rk[sa[i]] = ++p;
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> (s + 1); int n = strlen(s + 1);
    init(n); getlcp(n); stk[top = 1] = 1;
    for(int i = 2; i <= n; l[i] = stk[top], stk[++top] = i, i++)
        while(top && height[stk[top]] > height[i]) { r[stk[top]] = i, --top; }
    while(top) r[stk[top]] = n + 1, --top;
    ll res = (ll)(n - 1) * n * (n + 1) / 2;
    for(int i = 2; i <= n; i++)
        res -= 2ll * (r[i] - i) * (i - l[i]) * height[i];
    cout << res << '\n';
    return 0;
}