2024.8 #7

1.[TJOI2015] 弦论

你说得对，但是小 S 觉得 SAM 非常的不优美，所以她打算使用 SA 做。

她决定先研究 \(t = 0\) 的情况。

从头到尾扫，每一个后缀没出现过的子串数为是 \(n - sa_i + 1 - hight_i\)。然后就可以直接枚举每一个位置，然后就可以计算出第 \(k\) 个子串的结尾在哪里。

然后她需要考虑 \(t = 1\) 的情况。

此时她有一个暴论。同样的从前往后扫，然后枚举每一个末尾。但是这是 \(\mathrm O(n^2)\) 的，她很生气。

但是她发现了一个性质，那就是当前面的字母固定时，后面一个字母是单调不降的，满足单调性。所以她想到了用二分做。

她对于后缀数组做前缀和，这样就知道了一个字符为开头的子串有多少个了。那么就可以做了，复杂度为 \(\mathrm O(n \log n)\)，她很高兴。