题解：P9623 [ICPC2020 Nanjing R] Baby's First Suffix Array Problem

· · 题解

提供一个常数巨小且非常简单的 2log SA 做法。

基于 zltqwq 的这篇题解。

简单模拟一下两个字符串比大小的过程，即，求出 LCP 比较 LCP 后一位的字符大小。

对于后一位的字符大小我们可以通过原串上的 rk 求得。

因为有二维限制所以较为显然的对于 sa 数组上个分治，令 pre_i=\min_{j=i}^{mid} h_j,suf_i=\min_{j=mid-1}^i h_j。

那么跨过 mid 的区间 [l,r] LCP 可以表示为 \min\{pre_{rk_l+1},suf_{rk_r}\}。

那我们现在就可以按照 rk 和原串中的位置关系去分讨了。

  1. - $suf_{rk_k}<r-k+1$，这时候 LCP 一定小于 $r-k+1$，所以直接统计 $[l,k-1]$ 范围内的点数就行了。 - $suf_{rk_k}\ge r-k+1$，这时候我们要统计的实际就是 $pre_{i}<r-k+1$ 的 $i$ 的数量，直接和 $sa_i\in[l,k-1]$ 一起做就是一个二维数点，扫描线即可。

综上，我们得到了一个 cdq 分治套二维数点的两个 log 小常熟做法。

submission