题面
题解
$ ecause sum_{1 leq i < j leq n} i + j = frac{n(n-1)(n+1)}2 $
所以只需求$sum lcp(i,j)$即可。
$ ecause lcp(i,j)=min_{rank[i] leq k leq rank[j]}{height[k]} $
所以可以选用最小值分治算法：
int min[maxn];
long long ans;
void Div(int l, int r)
{
if(l == r) return (void)(ans += height[l]);
int mid = (l + r) >> 1;
Div(l, mid); Div(mid + 1, r);
min[mid] = height[mid];
min[mid + 1] = height[mid + 1];
for(RG int i = mid - 1; i >= l; i--)
min[i] = std::min(min[i + 1], height[i]);
for(RG int i = mid + 2; i <= r; i++)
min[i] = std::min(min[i - 1], height[i]);
int j = mid;
for(RG int i = mid; i >= l; i--)
{
while(j < r && min[j + 1] >= min[i]) ++j;
ans += 1ll * min[i] * (j - mid);
}
j = mid + 1;
for(RG int i = mid + 1; i <= r; i++)
{
while(j > l && min[j - 1] > min[i]) --j;
ans += 1ll * min[i] * (mid + 1 - j);
}
}
//...
Div(1, n);
但是我们要精益求精，我们可以想一想$O(n)$的算法。
用栈维护前面与$i$最近且小于等于$height[i]$的元素$p$
则转移方程为：
$ f[i]=f[p]+(i-p) imes height[i] $
//...
long long f[maxn];
struct node { int val, pos; };
std::stack<node> stk;
int main()
{
//...
long long ans = 0; int pos = 0;
for(RG int i = 1; i <= n; i++)
{
int p = pos;
while(!stk.empty() && stk.top().val > height[i]) stk.pop();
if(!stk.empty()) p = stk.top().pos;
ans += (f[i] = f[p] + (i - p) * height[i]);
if(!height[i]) pos = i;
stk.push((node){height[i], i});
}
}
代码
#include<cstdio>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<stack>
#define RG register
#define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define clear(x, y) memset(x, y, sizeof(x))
inline int read()
{
int data = 0, w = 1; char ch = getchar();
while(ch != '-' && (!isdigit(ch))) ch = getchar();
if(ch == '-') w = -1, ch = getchar();
while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar();
return data * w;
}
const int maxn(500010);
char s[maxn];
int n, sa[maxn], rank[maxn], height[maxn];
void sort(int m)
{
static int t[maxn], t2[maxn], c[maxn];
int i, *x = t, *y = t2, p = 0;
std::fill(c + 1, c + m + 1, 0);
for(i = 1; i <= n; i++) ++c[x[i] = s[i]];
for(i = 1; i <= m; i++) c[i] += c[i - 1];
for(i = n; i; i--) sa[c[x[i]]--] = i;
for(RG int k = 1; k <= n && p < n; k <<= 1)
{
p = 0;
for(i = n - k + 1; i <= n; i++) y[++p] = i;
for(i = 1; i <= n; i++) if(sa[i] > k) y[++p] = sa[i] - k;
std::fill(c + 1, c + m + 1, 0);
for(i = 1; i <= n; i++) ++c[x[y[i]]];
for(i = 1; i <= m; i++) c[i] += c[i - 1];
for(i = n; i; i--) sa[c[x[y[i]]]--] = y[i];
std::swap(x, y), p = 1, x[sa[1]] = 1;
for(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;
m = p;
}
}
void get_height()
{
int k = 0;
for(RG int i = 1; i <= n; i++) rank[sa[i]] = i;
for(RG int i = 1; i <= n; i++)
{
if(k) --k;
int j = sa[rank[i] - 1];
while(s[i + k] == s[j + k]) ++k;
height[rank[i]] = k;
}
}
long long f[maxn];
struct node { int val, pos; };
std::stack<node> stk;
int main()
{
#ifndef ONLINE_JUDGE
file(cpp);
#endif
scanf("%s", s + 1); n = strlen(s + 1);
sort(130); get_height();
long long ans = 0; int pos = 0;
for(RG int i = 1; i <= n; i++)
{
int p = pos;
while(!stk.empty() && stk.top().val > height[i]) stk.pop();
if(!stk.empty()) p = stk.top().pos;
ans += (f[i] = f[p] + (i - p) * height[i]);
if(!height[i]) pos = i;
stk.push((node){height[i], i});
}
printf("%lld
", 1ll * n * (n - 1) * (n + 1) / 2 - ans * 2);
return 0;
}