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

lzyqwq · 2023-12-20 21:22:34 · 题解

我永远喜欢数据结构

很神仙的串串题，第一次见这种做法。在 CF 上应该能评个 \ge \color{maroon}{*3300}。当时场上想假了直接对着这玩意冲成小丑了。百度上只搜到了后缀树的题解，你谷的一篇后缀数组题解可能是因为作者太神仙了所以讲的比较简略，这里来一篇详细一点的后缀数组题解。

长文码字不易，有笔误还请耐心指出 /bx。

题目传送门

• 给出长度为 n 的字符串 s，m 组询问对 s[l,r] 这个子串进行后缀排序后，（这个子串的）后缀 s[k,r] 的排名。排名定义为比它小的后缀的个数 +1。

• 多组数据，记 N=\sum n，M=\sum m，N,M\le 5\times 10^4。

这个 N\le 5\times 10^4 和 \text{5.00\,s} 时限是不是为了放时间复杂度 \mathcal{O}((N+M)\log^3 N) 的做法过啊，是的话就太不牛了 /qd。

先对原串进行后缀排序。

考虑从排名的定义入手，求出子串中有多少个后缀比询问的后缀小。对于这些子串中的后缀，考虑找到它们在原串中的后缀，尝试寻找充要条件。

设有（子串的）后缀 s[i,r]，其中 i\in[l,k)\bigcup \,(k,r]。按两类情况考虑。

• rk_i<rk_k

  此时 s[i,r]<s[k,r]，当且仅当 \boldsymbol{i<k} 且 \bold{|LCP}\boldsymbol{(s[i,n],s[k,n])|\le r-k}，或 \boldsymbol{i>k}。

  • 充分性

    当 i<k 且 |\text{LCP}(s[i,n],s[k,n])|\le r-k 时，两个后缀第一个不同的位置一定均在 s[i,r] 和 s[k,r] 中出现，此时比较两个串也是比较这两位，因为 rk_i<rk_k，故 s[i,r]<s[k,r]。

    当 i>k 时，若两个后缀第一个不同的位置均在 [l,r] 中出现则与上一种情况合理，否则 s[i,r] 是 s[k,r] 的前缀，故 s[i,r]<s[k,r]。

  • 必要性

    考虑 s[i,r]<s[k,r] 时，若 i<k，则一定有 |\text{LCP}(s[i,n],s[k,n])|\le r-k，否则 s[k,r] 为 s[i,r] 前缀，此时 s[k,r]<s[i,r]。若 i>k，则已经满足条件。

  • 做法

    分 i<k 和 i>k 讨论。

    若 i<k，则需要统计有多少个后缀 s[i,n] 满足 i\in[l,k)，rk_i<rk_k 且 \text{|LCP}(s[i,n],s[k,n])|\le r-k。降第三个限制转化为 \text{height} 数组的限制，其等价于 \min\limits_{j=rk_i+1}^{rk_k}\text{height}_j\le r-k。容易发现此时满足条件的 i 的 rk_i 在一个前缀 [1,x] 中，其中 x<rk_k。二分 + RMQ 求出这个 x，问题转化成统计有多少个点对满足 i\in[l,k) 且 rk_i\in[1,x]，主席树维护即可。

    若 i>k，则需要统计有多少个后缀 s[i,n] 满足 i\in(k,r] 且 rk_i<rk_k，同样主席树维护。

• rk_i>rk_k

  此时 s[i,r]<s[k,r]，当且仅当 \boldsymbol{i>k} 且 \bold{|LCP}\boldsymbol{(s[i,n],s[k,n])|\ge r-i+1}。

  • 充分性

    容易发现此时 s[i,r] 为 s[k,r] 前缀，故 s[i,r]<s[k,r]。

  • 必要性

    考虑证明不满足上述条件则 s[i,r]>s[k,r]。

    若 i<k，如果两个串第一个不同的位置均在 [l,r] 中出现，因为 rk_k<rk_i，所以 s[i,r]>s[k,r]。否则，s[k,r] 为 s[i,r] 前缀，此时 s[i,r]>s[k,r]。

    若 i>k 且 \text{|LCP}(s[i,n],s[k,n])|\le r-i，则两个串第一个不同的位置一定均在 [l,r] 中出现，因为 rk_k<rk_i，所以 s[i,r]>s[k,r]。

  • 做法（本题解最核心部分）

    以排名为下标做一遍序列分治，将询问挂在 rk_k 上，每层分治考虑右半边对左半边的贡献（很像 cdq 分治）并左右递归下去统计，则对于任意一个合法的后缀，根据分治树的形态，一定存在且仅存在一层分治，使得询问在左半边，后缀在右半边，此时它被统计到。并且，在每层分治中我们统计合法的贡献，可以做到不重不漏。

    设分治区间为 [L,R]，中点 mid=\left\lfloor\dfrac{L+R}{2}\right\rfloor。

    对于左半边的一个询问 (l,r,k)，我们要统计右半边有多少个 i，满足：

    • sa_i\in(k,r]
    • \text{|LCP}(s[k,n],s[sa_i,n])|\ge r-sa_i+1\Leftrightarrow \min\limits_{j=rk_k+1}^i \text{height}_j\ge r-sa_i+1

    采用序列分治的一般套路，从 mid\rightarrow L 扫描询问。设当前扫到的排名为 K。维护变量 mn=\min\limits_{j=K+1}^{mid}\text{height}_j。对于右半区间维护前缀 \text{height} 最小值，即 pmn_i=\min\limits_{j=mid+1}^{i}\text{height}_j。则对于当前扫到的排名上的询问，条件中的 \min\limits_{j=rk_k+1}^i \text{height}_j\ge r-i+1 可以转化为 \min\{mn,pmn_i\}。

    容易发现 pmn_i 具有单调（不升）性。可以找到一个分界点 p，使得当 i\in[mid+1,p) 时，\min\{mn,pmn_i\}=mn；当 i\in[p,R] 时，\min\{mn,pmn_i\}=pmn_i。

    对于分界点左边的情况，就是统计有多少 i 满足：

    • sa_i\in(k,r]
    • mn \ge r-sa_i+1\Leftrightarrow sa_i\ge r-mn+1
    • i\in[mid+1,p)

    整理一下就是：

    • sa_i\in[\max\{r-mn,k\}+1,r]
    • i\in[mid+1,p)

    容易主席树维护。

    对于分界点右边的情况，就是统计有多少 i 满足：

    • sa_i\in(k,r]
    • pmn_i\ge r-sa_i+1\Leftrightarrow sa_i+pmn_i\ge r+1
    • i\in [p,R]

    你发现这是个三维数点，好像行不通啊！

    然后就是一个很妙的转化了。考虑正难则反。你发现对于分界点右边的情况，sa_i+pmn_i\ge r+1\Rightarrow sa_i+mn\ge r+1，因为在分界点右边 pmn_i=\min\{pmn_i,mn\}。所以可以先统计满足以下条件的 i 的个数：

    • sa_i\in[\max\{r-mn,k\}+1,r]
    • i\in [p,R]

    算上分界点左边的统计，相当于要统计右半边满足 sa_i\in[\max\{r-mn,k\}+1,r] 的 i 个数。可以 vector + 二分统计。考虑哪些不合法的被统计了，显然它满足：

    • sa_i\in[\max\{r-mn,k\}+1,r]
    • sa_i+pmn_i\le r
    • i\in[p,R]

    于是就要减去这样的 i 的个数。实际上这还是个三维数点，不过你发现，\boldsymbol{\nexists\,i\in[mid+1,p),sa_i\in[\max\{r-mn,k\}+1,r]\land sa_i+pmn_i\le r}。即分界点左边不存在满足前两个条件的 i。

    为什么呢？首先 sa_i\in[\max\{r-mn,k\}+1,r] 的必要条件是 sa_i\ge r-mn+1。你考虑分界点左边 mn\le pmn_i，若 sa_i\ge r-mn+1 即 sa_i+mn\ge r+1，则一定有 sa_i+pmn_i\ge r+1。反之，若 sa_i+pmn_i\le r，则一定有 sa_i+mn \le r 即 sa_i\le r-mn。因此两个条件不能被同时满足。

    所以我们直接大胆忽略 i\in[p,R] 这个条件，统计全局（当前分治区间） sa_i\in[\max\{r-mn,k\}+1,r] 且 sa_i+pmn_i\le r 的 i 的个数。同样是二维数点，主席树维护即可。

至此两类统计都解决了。接下来算复杂度。因为有主席树和 ST 表，所以空间复杂度显然为 \mathcal{O}(N\log N)。

至于时间复杂度（只说每个部分的瓶颈），后缀排序是 \mathcal{O}(N\log^2 N) 的（因为不是瓶颈所以没用基数排序优化）。rk_i<rk_k 的统计需要往主席树中插入 \mathcal{O}(N) 个点对，并且每次询问要进行一次 \mathcal{O}(1) 检查（ST 表）的二分以及 \mathcal{O}(\log N) 的主席树查询，时间复杂度为 \mathcal{O}((N+M)\log N)。

对于分治部分，每个询问会在 \mathcal{O}(\log N) 层分治中被扫到，每次扫到要做一次主席树查询和 vector 二分，单次是 \mathcal{O}(\log N)。每个点对会在 \mathcal{O}(\log N) 层分治中被插入主席树，单次也是 \mathcal{O}(\log N)。这部分的时间复杂度为 \mathcal{O}((N+M)\log^2 N)。为了维护主席树，每层分治需要将点对进行排序，由于每层分治的区间总长度为 N，因此任意一层排序的 \log 不超过 \mathcal{O}(\log N)。容易通过乘法分配律得到是 \mathcal{O}(N\log^2 N) 的。因此，分治部分的总时间复杂度为 \mathcal{O}((N+M)\log ^2 N)。

综上，本做法时间复杂度为 \mathcal{O}((N+M)\log^2 N)，空间复杂度为 \mathcal{O}(N\log N)，可以接受。

代码

AC 记录

完结撒花！