只需要算出本质不同子串数和 $a$ 是 $b$ 子串的方案数即可。依次加入每个字符，假设当前加入了第 $i$ 个字符，则存在一个 $j$ 使得 $s[1,i],\ldots,s[j,i]$ 是未出现过的子串。对于之前出现的某个子串，设其最后一次出现位置的左端点为 $k$，则其贡献为 $\min\{j,k\}$。用 SAM + LCT + 线段树维护即可。
时间复杂度 $O(|s|\log^2|s|)$。
QOJ.ac
QOJ
Discussion #239 for Problem #12342. Incomparable Pairs
Type: Editorial
Status: Open
Posted by: jiangly
Posted at:
Last updated:
题解
Comments
No comments yet.