洛谷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;
}