P4248 [AHOI2013]差异

(color{#0066ff}{题目描述})

给定一个长度为 (n) 的字符串 (S)，令 (T_i) 表示它从第 (i) 个字符开始的后缀。求

(displaystyle sum_{1leqslant i<jleqslant n} ext{len}(T_i)+ ext{len}(T_j)-2 imes ext{lcp}(T_i,T_j))

其中，( ext{len}(a)) 表示字符串 (a) 的长度，( ext{lcp}(a,b)) 表示字符串 (a) 和字符串 (b) 的最长公共前缀。

(color{#0066ff}{输入格式})

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

(color{#0066ff}{输出格式})

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

(color{#0066ff}{输入样例})

cacao

(color{#0066ff}{输出样例})

(color{#0066ff}{数据范围与提示})

对于 100% 的数据，保证 (2leqslant nleqslant 500000)，且均为小写字母

(color{#0066ff}{题解})

定义H为排名为i-1和i的字符串的LCP

我们有(H[i] geq H[i-1] - 1)

还有(LCP(i,j)=min(LCP(i,k),LCP(k,j)))

(egin{aligned}LCP(i,j)=min_{i+1leq k leq j}(H[k]) end{aligned})

这里就不证明了其实我不会

所以把大的(Sigma)拆开

前两部分可以直接统计

后面的LCP可以先求出H，然后单调栈求出每个数作为最小值对于区间的贡献

不看LL见祖宗

#include <bits/stdc++.h>

typedef long long LL;

const int maxn = 5e5 + 100;
const int inf = 0x7fffffff;

int n ,m;
int H[maxn], c[maxn], x[maxn], y[maxn], sa[maxn], rk[maxn];
LL l[maxn], r[maxn];
char s[maxn];
LL ans1, ans2, ans3;

class stack {
private:
    int st[maxn], tp;
public:
    void pop() { tp--; }
    int top() { return st[tp]; }
    void push(int x) { st[++tp] = x; }
    void clr() { memset(st, 0, sizeof st); }
}S;

LL getans(LL t) {
    return (t * (t + 1LL)) >> 1LL;
}

void predoit() {
    for(int i = 1; i <= n; i++) c[x[i] = s[i]]++;
    for(int i = 1; i <= m; i++) c[i] += c[i - 1];
    for(int i = n; i >= 1; i--) sa[c[x[i]]--] = i;
    for(int k = 1; k <= n; k <<= 1) {
        int num = 0;
        for(int i = n - k + 1; i <= n; i++) y[++num] = i;
        for(int i = 1; i <= n; i++) if(sa[i] > k) y[++num] = sa[i] - k;
        for(int i = 1; i <= m; i++) c[i] = 0;
        for(int i = 1; i <= n; i++) c[x[i]]++;
        for(int i = 1; i <= m; i++) c[i] += c[i - 1];
        for(int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i], y[i] = 0;
        std::swap(x ,y);
        x[sa[1]] = 1, num = 1;
        for(int i = 2; i <= n; i++) 
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k])? num : ++num;
        if(num == n) break;
        m = num;
    }
    for(int i = 1; i <= n; i++) rk[i] = x[i];
    int h = 0;
    for(int i = 1; i <= n; i++) {
        if(rk[i] == 1) continue;
        if(h) h--;
        int j = sa[rk[i] - 1];
        while(j + h <= n && s[i + h] == s[j + h]) h++;
        H[rk[i]] = h;
    }
}

void work_contribute() {
    S.push(1);
    H[1] = -inf;
    for(int i = 2; i <= n; i++) {
        while(H[S.top()] >= H[i]) S.pop();
        l[i] = S.top();
        S.push(i);
    }
    S.clr();
    S.push(n + 1);
    H[n + 1] = -inf;
    for(int i = n; i >= 2; i--) {
        while(H[S.top()] > H[i]) S.pop();
        r[i] = S.top();
        S.push(i);
    }
    for(LL i = 2LL; i <= n; i++) ans3 += (i - l[i]) * (r[i] - i) * H[i];
}

void query() {
    ans3 <<= 1LL;
    for(LL i = n; i >= 1; i--) ans1 += i * (i - 1LL);
    for(int i = n - 1; i >= 1; i--) ans2 += getans(i);
    printf("%lld", ans1 - ans3 + ans2);
}

int main() {
    scanf("%s", s + 1);
    n = strlen(s + 1), m = 122;
    predoit();
    work_contribute();
    query();
    return 0;
}