搬的学习笔记，之前没想过要新开一篇。
给出一个字符串 \(s\)，有 \(q\) 次询问，第 \(i\) 次询问给出 \(l_i,r_i,t_i\)，求一个字典序最小的字符串 \(str\)，使得它是 \(s[l_i,r_i]\) 的子串，且 \(str>t_i\)。
\(|s|\le 10^5\)，\(\sum\limits_{i=1}^q|t_i|,q\le 2\times 10^5\)。
记 \(|\text{LCP}(str,t_i)|=l\)，\(str>t_i\) 当且仅当 \(str_{l+1}>t_{i_{l+1}}\)，为了使 \(str\) 尽量小，我们希望 \(\boldsymbol l\) 尽量大。
证明很简单，假设有一个串 \(T\) 满足 \(\text{LCP}(T,t_i)=L<l\)，则 \(\bf {LCP}\boldsymbol{(str,T)=L}\)，且 \(\boldsymbol{T_{L+1}>str_{L+1}}\)，因此 \(\boldsymbol{T>str}\)，所以 \(\bf{|LCP|}\) 大的字符串字典序更小。
先将 \(s\) 和所有 \(t_i\) 中间用奇怪字符拼接成大串 \(S\)，这样不改变任意两个后缀的 \(\text{LCP}\)。然后做一遍后缀排序，求出 \(sa,rk,\text{height}\) 数组以及维护 ST 表辅助求后缀之间的 \(|\text{LCP}|\)。
对于每一组询问，考虑枚举 \(l\,(0\le l \le r_i-l_i)\) 以及下一位拼上什么字符 \(c\)，满足 \(c>t_{i_{l+1}}\)（一定是仅拼上一个字符，因为空字符字典序最小）。可以先二分 + ST 表求出与 \(t_i\) 在 \(S\) 中的后缀的 \(|\text{LCP}|\) 至少为 \(l\) 的后缀排名区间 \([L,R]\)。那么在 \(\text{LCP}\) 末尾拼上一个字符 \(c\) 后（记这个字符串为 \(p\)），以 \(p\) 为前缀的后缀的排名仍然是一个连续的区间。由于后缀排序过，因此 \([L,R]\) 排名区间内的后缀的第 \(l+1\) 位的字符一定单调不减。
考虑继续二分出这个连续区间 \([ql,qr]\)，可以二分找到最小的排名 \(mn\) 使得 \(S_{sa_{mn}+l}\ge c\) 以及最大的排名 \(mx\) 使得 \(S_{sa_{mx}+l}\le c\)。则 \(ql=mn,qr=mx\)。若不存在 \([ql,qr]\) 这个区间，则跳过。
我们要求 \(s[l_i,r_i]\) 中是否存在一个子串 \(str\) 以 \(p\) 为前缀，相当于求 \(suf_{l_i}\sim suf_{r_i-l}\) 这些后缀中，是否存在一个后缀 \(suf_j\) 使得 \(ql\le j\le qr\)。至此原问题转化成了二维数点，用主席树维护即可。
可以从小到大枚举 \(c\)，对于枚举的 \(l\)，我们找到一个最小的字符 \(c\) 满足条件之后，即可停止当前 \(l\) 的枚举。因为要求字典序最小。
对于多种 \(l\) 的答案，上面已经说过，选最大的那一种。
默认 \(|S|,q\) 同阶，时间复杂度为 \(\mathcal{O}(|\Sigma|\cdot (\sum_{i=1}^q|t_i|)\log |S|+|S|\log^2 |S|)\)，空间复杂度为 \(\mathcal{O}(|S|\log |S|)\)。由于不是瓶颈，后缀排序部分未使用基数排序优化。
标签：字符,le,LCP,记录,后缀,text,CF1037H,str,Security From： https://www.cnblogs.com/MnZnOIerLzy/p/17870835.html