只需要算出本质不同子串数和 $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
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
Discussion #239 for Problem #12342. Incomparable Pairs
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-13 00:26:00
Last updated: 2025-12-13 00:26:03
题解
Comments
No comments yet.