P9623 Babys First Suffix Array Problem

· · 题解

对原串求后缀数组。下面考察区间 \rm SA 和原串 \rm SA 的关系。

对于区间 [l,r] 与内部的两个位置 i<j，考察区间内部 i 后缀与 j 后缀的大小关系。

如果原串 j 的排名小于 i 的排名，那么区间内 j 的排名也小于 i 的排名；如果原串 j 的排名大于 i 的排名，当 [j,n] 和 [i,n] 的 \rm LCP 小于等于 r-j 时，区间内存在使得 j 的字典序大于 i 字典序的判据，j 的排名仍然大于 i 的排名；否则 j 的排名小于 i 的排名。

把所有询问离线下来，在原串排名序列上做 \rm CDQ 分治。具体来说，我们把 k 处的询问挂在下标 rk_k 上，每次统计右半部分对左半部分的贡献。具体来说，我们求出对于左侧的每个询问，右侧有几个位置为它贡献。考虑两侧的两个位置 i,j，与 i 上的询问 [l,r]，由上面的讨论，j 为 i 做贡献（j 在区间内的字典序小于 i）的条件是：

把 $(sa_j,c_j)$ 放到二维平面上去，右侧的问题是朴素的；前者则是让我们求出一个直角梯形内或是三角形内的点数。注意到这个直角梯形或三角形的角一定在 $x$ 轴上，差分成一个贴着 $x$ 轴的矩形和一个贴着 $x$ 轴的等腰直角三角形，对于这个等腰直角三角形，考虑从一侧扫描线，就只用维护一维偏序，分别用两个 $\rm BIT$ 就好，另一边也可以类似地做。 然后再考虑左到右的贡献，两个排名，$i<j$，$i$ 为 $j$ 做贡献的条件是 $sa_i\in[l,r],sa_i>sa_j$ 或 $sa_i\in[l,r],sa_i<sa_j$ 且 ${\rm LCP}(i,j)\leq r-sa_j$，转化成 $sa_i\in[\max\{sa_j+1,l\},r]$ 与 $sa_i\in[l,\min\{r,sa_j-1\}]$ 与 $\min\{e,c_i\}\leq r-sa_j$ 可以类似地处理。 复杂度 $O(n\log^2n)$。 [参考代码。](https://www.luogu.com.cn/paste/7b5qaein)