[AHOI2013]差异

题意：

给定一个长度为 $n$ 的字符串 $S$ ，令 $T_{i}$ 表示它从第 $i$ 个字符开始的后缀，求

$\sum_{1 \leq i < j \leq n} l e n (T_{i}) + l e n (T_{j}) - 2 \times l c p (T_{i}, T_{j})$

由于直接算答案不是很好做，考虑先求出 $\sum_{1 \leq i < j \leq n} l e n (T_{i}) + l e n (T_{j})$ 再减去后面那堆东西。

这部分答案为 $\frac{n (n - 1) (n + 1)}{2}$ （每个后缀都出现了 $n - 1$ 次，后缀总长是 $\frac{n (n + 1)}{2}$ ）

之后考虑怎么搞 $l c p (i, j)$ 这项，我们知道 $l c p (i, j) = k$ 等价于 $min h e i g h t [i + 1 \dots j] = k$

所以可以将 $l c p (i, j)$ 记作 $Missing or unrecognized delimiter for \left$ 对答案的贡献。

考虑每个位置对答案的贡献是哪些后缀的 $LCP$ ，其实就是从它开始向左若干个连续的 $height$ 大于它的后缀选一个，再从向右若干个连续个 $height$ 不小于它的后缀中选一个。这个东西可以单调栈搞。

虽然写的时候偷懒直接搞了个悬线法。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


signed main()
{
	scanf("%s",str+1);
	n=strlen(str+1);ans=1ll*(n+1)*n*(n-1)/2;
	R(i,1,n) s[i]=str[i]-'a'+2;
	get_SA(s,sa,rk,n),get_ht(n,ht);ht[n+1]=-1;
	R(i,1,n) l[i]=r[i]=i;
	R(i,1,n) while(ht[l[i]-1]>ht[i]) l[i]=l[l[i]-1];
	L(i,1,n) while(ht[r[i]+1]>=ht[i]) r[i]=r[r[i]+1];
	R(i,1,n) ans-=2ll*ht[i]*(i-l[i]+1)*(r[i]-i+1);
	//L(i,1,n) printf("%lld %lld %lld %lld\n",i,i-l[i]+1,r[i]-i+1,ht[i]);
	printf("%lld\n",ans);
}

文章目录