[AHOI 2013] 差异

发表于2017-04-14更新于2020-08-06

题目大意

长度为 nn 的字符串 SS，记 TiT_i 为其从第 ii 个字符开始的后缀，求：

∑1⩽i<j⩽nlen(Ti)+len(Tj)−2  lcp(Ti,  Tj)\sum_{1 \leqslant i < j \leqslant n} len(T_i) + len(T_j) - 2 \; lcp(T_i, \; T_j)

1⩽n⩽500,0001 \leqslant n \leqslant 500,000

题目链接

【AHOI 2013】差异 - Luogu 4248

题解

将所求式分成两部分。

第一部分易得为：

∑1⩽i<j⩽nlen(Ti)+len(Tj)=(n−1)×n(n+1)2\sum_{1 \leqslant i < j \leqslant n} len(T_i) + len(T_j) = (n - 1) \times \frac{n (n + 1)}2

因为每个后缀均被枚举了 n−1n - 1 次。

第二部分（不管系数），由后缀数组中 heightheight 数组的性质可化为：

\begin{align} \sum_{1 \leqslant i < j \leqslant n} lcp(T_i, \; T_j) &= \sum_{1 \leqslant i < j \leqslant n} min(height[k]), \; k \in [rank[i] + 1, \; rank[j]] \\ &= \sum_{1 \leqslant i < j \leqslant n} min(height[k]), \; k \in [i + 1, \; j] \end{align}

即所有区间的  height height的最小值。暴力求解显然会 TLE。

枚举区间的结尾 ii，在这之前比 height[i]height[i] 大的值都不会对答案产生影响，考虑维护一个 heightheight 单调栈（说来在这道题里，它只进不出的，说单调队列也没错。。。）记录 ii。

当考虑到 ii 对答案的贡献时，记在 ii 之前第一个满足 height[j]⩽height[i]height[j] \leqslant height[i] 的 jj，区间开头在 [j+1,  i][j + 1, \; i] 内的区间的最小值均为 height[i]height[i]，即对答案的贡献为 (i−j)×height[i](i - j) \times height[i]。从头枚举一遍即可。

代码

就是这道题，让我换了后缀数组的版子，因为，这个版子理解起来容易一些（后缀数组的代码终于不用背了！）。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <cstdio>
#include <cstring>
#include <stack>
const int MAXN = 500005;
namespace SuffixArray {
    int rank[MAXN], sa[MAXN], height[MAXN], n;
    char str[MAXN];
    void buildSA(int m) {
        static int fir[MAXN], sec[MAXN], temp[MAXN], cnt[MAXN], i;
        n = strlen(str) + 1;
        str[n - 1] = 0;
        memset(cnt, 0, sizeof cnt);
        for (i = 0; i < n; i++) cnt[(int) str[i]]++;
        for (i = 1; i < m; i++) cnt[i] += cnt[i - 1];
        for (i = 0; i < n; i++) rank[i] = cnt[(int) str[i]] - 1;
        for (int l = 1; l < n; l <<= 1) {
            for (int i = 0; i < n; i++)
                fir[i] = rank[i], sec[i] = i + l < n ? rank[i + l] : 0;
            memset(cnt, 0, sizeof cnt);
            for (i = 0; i < n; i++) cnt[sec[i]]++;
            for (i = 1; i < n; i++) cnt[i] += cnt[i - 1];
            for (i = n - 1; ~i; i--) temp[--cnt[sec[i]]] = i;
            memset(cnt, 0, sizeof cnt);
            for (i = 0; i < n; i++) cnt[fir[i]]++;
            for (i = 1; i < n; i++) cnt[i] += cnt[i - 1];
            for (i = n - 1; ~i; i--) sa[--cnt[fir[temp[i]]]] = temp[i];
            bool unique = true;
            rank[sa[0]] = 0;
            for (i = 1; i < n; i++) {
                rank[sa[i]] = rank[sa[i - 1]];
                if (fir[sa[i]] == fir[sa[i - 1]] && sec[sa[i]] == sec[sa[i - 1]]) 
                    unique = false;
                else rank[sa[i]]++;
            }
            if (unique) break;
        }
    }
    void getHeight() {
        int k = 0;
        for (int i = 0; i < n - 1; i++) {
            k ? k-- : 0;
            int j = sa[rank[i] - 1];
            while (str[i + k] == str[j + k]) k++;
            height[rank[i]] = k;
        }
    }
}
int main() {
    char *str = SuffixArray::str;
    scanf("%s", str);
    int n = strlen(str);
    SuffixArray::buildSA(128);
    SuffixArray::getHeight();
    int *height = SuffixArray::height + 1;
    long long ans = 0;
    std::stack<int> s;
    s.push(0);
    static long long f[MAXN];
    for (int i = 1; i < n; i++) {
        while (!s.empty() && height[s.top()] > height[i]) s.pop();
        ans += f[i] = f[s.top()] + (long long) (i - s.top()) * height[i];
        s.push(i);
    }
    printf("%lld\n", (long long) (n - 1) * n * (n + 1) / 2 - 2 * ans);
    return 0;
}