3238: [Ahoi2013]差异

3238: [Ahoi2013]差异

Time Limit: 20 Sec   Memory Limit: 512 MB Submit: 2106   Solved: 953 [ Submit][ Status][ Discuss]

Description

Input

一行，一个字符串S

Output

 

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

Sample Input

cacao

Sample Output

54

HINT

2<=N<=500000,S由小写英文字母组成

Source

[ Submit][ Status][ Discuss] 构造一个后缀数组，两个后缀的lcp就是在这个数组走过去时取min，单调队列瞎搞即可 写这个真的想吐。。。 #include<iostream> #include<cstdio> #include<queue> #include<vector> #include<bitset> #include<algorithm> #include<cstring> #include<map> #include<stack> #include<set> #include<cmath> #include<ext/pb_ds/priority_queue.hpp> using namespace std; const int maxn = 5E5 + 50; typedef long long LL; int n,m,co[maxn],t[maxn],t2[maxn],height[maxn] ,l[maxn],r[maxn],q[maxn],rank[maxn],sa[maxn]; char ch[maxn]; LL ans = 0; void Getsa() { int *x = t,*y = t2; m = 26; for (int i = 1; i <= n; i++) ++co[x[i] = ch[i]]; for (int i = 2; i <= m; i++) co[i] += co[i-1]; for (int i = n; i; i--) sa[co[x[i]]--] = i; for (int k = 1; k < n; k <<= 1) { int p = 0; for (int i = n; i > n - k; i--) y[++p] = i; for (int i = 1; i <= n; i++) if (sa[i] - k > 0) y[++p] = sa[i] - k; for (int i = 1; i <= m; i++) co[i] = 0; for (int i = 1; i <= n; i++) ++co[x[y[i]]]; for (int i = 2; i <= m; i++) co[i] += co[i-1]; for (int i = n; i; i--) sa[co[x[y[i]]]--] = y[i]; swap(x,y); x[sa[1]] = (p = 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]?p:++p; if (p == n) break; m = p; } } void Rank_and_Height() { for (int i = 1; i <= n; i++) rank[sa[i]] = i; int k = 0; for (int i = 1; i <= n; i++) { if (k) --k; int j = sa[rank[i]-1]; while (ch[i + k] == ch[j + k]) ++k; height[rank[i]] = k; } } int main() { #ifdef DMC freopen("DMC.txt","r",stdin); #endif scanf("%s",ch + 1); n = strlen(ch + 1); for (int i = 1; i <= n; i++) ch[i] = ch[i] - 'a' + 1; Getsa(); Rank_and_Height(); int tail = 0; q[tail = 1] = 0; for (int i = 1; i <= n + 1; i++) { while (tail && height[q[tail]] > height[i]) r[q[tail--]] = i-1; q[++tail] = i; } while (tail) r[q[tail--]] = n; q[tail = 1] = n + 1; for (int i = n; i >= 0; i--) { while (tail && height[q[tail]] >= height[i]) l[q[tail--]] = i+1; q[++tail] = i; } while (tail) l[q[tail--]] = 1; for (int i = 2; i <= n; i++) ans -= 2LL*height[i]*(i-l[i]+1LL)*(r[i]-i+1LL); LL K = 1LL*(1+n)*n/2LL; cout << K*1LL*(n-1LL) + ans; return 0; }