DDOSvoid's Blog

Luogu P4248 [AHOI2013]差异

发表于 分类于
本文字数： 1.8k 阅读时长 ≈ 2 分钟

题目描述

https://www.luogu.com.cn/problem/P4248

简要题意：给定一个长度为 $n$ 的字符串 $S$，求 $\sum_{1\le i<j\le n}len(suf(S,i))+len(suf(S,j))-2lcp(suf(S,i),suf(S,j))$

$n\le 5\times 10^5$

Solution

前面那个东西显然是 $\frac{(n-1)n(n+1)}{2}$，后面那个东西就是 $\sum_{1\le i<j\le n}lcp(i,j)$，换句话就是 $H$ 的所有子区间的 $min$ 的和，这个可以用单调栈来求

时间复杂度 $O(n\log n)$

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
#include <iostream>
#include <stack>
#include <cstring>
#define maxn 500010
#define ll long long
#define INF 1000000000
using namespace std;

int n, k;
char s[maxn];

int tax[maxn], tp[maxn], sa[maxn], rk[maxn], M = 255;
void rsort() {
    for (int i = 0; i <= M; ++i) tax[i] = 0;
    for (int i = 1; i <= n; ++i) ++tax[rk[i]];
    for (int i = 1; i <= M; ++i) tax[i] += tax[i - 1];
    for (int i = n; i; --i) sa[tax[rk[tp[i]]]--] = tp[i];
}

int H[maxn]; 
void init_sa() {
    if (n == 1) return sa[1] = rk[1] = 1, void(); int cnt = 1; 
    for (int i = 1; i <= n; ++i) rk[i] = s[i], tp[i] = i; rsort();
    for (int k = 1; k < n; k *= 2) {
        if (cnt == n) break; M = cnt; cnt = 0;
        for (int i = n - k + 1; i <= n; ++i) tp[++cnt] = i;
        for (int i = 1; i <= n; ++i) if (sa[i] > k) tp[++cnt] = sa[i] - k;
        rsort(); swap(rk, tp); rk[sa[1]] = cnt = 1;
        for (int i = 2; i <= n; ++i) {
            if (tp[sa[i - 1]] != tp[sa[i]] || tp[sa[i - 1] + k] != tp[sa[i] + k]) ++cnt;
            rk[sa[i]] = cnt;
        }
    } int lcp = 0;
    for (int i = 1; i <= n; ++i) {
        if (lcp) --lcp;
        int j = sa[rk[i] - 1];
        while (s[j + lcp] == s[i + lcp]) ++lcp;
        H[rk[i]] = lcp;
    } 
}

int l[maxn], r[maxn];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> s + 1; n = strlen(s + 1); init_sa();
    stack<int> S; S.push(0); H[0] = H[n + 1] = -1; 
    for (int i = 1; i <= n + 1; ++i) {
        while (!S.empty() && H[i] < H[S.top()])
            r[S.top()] = i, S.pop();
        l[i] = S.top(); S.push(i); 
    } ll ans = 1ll * n * (n - 1) * (n + 1) / 2; 
    for (int i = 1; i <= n; ++i) ans -= 2ll * H[i] * (r[i] - i) * (i - l[i]);
    cout << ans << "\n";
    return 0;
}