感觉 \(\color{maroon} *3400\) 虚高，但是第一眼不会做 /ng。太菜了。
给出两个字符串 \(s,t\)，记 \(r_i\) 表示在 \(s_i\) 和 \(s_{i+1}\) 插入 \(t\) 得到的字符串。若 \(i=0\) 表示在开头插入，若 \(i=|s|\) 表示在结尾插入。
形式化的，\(r_i=\overline{s_1\dots s_it_1\dots t_{|t|}s_{i+1}\dots s_{|s|}}\)。
有 \(q\) 次询问，每次询问给出 \(l,r,k,x,y\)。你需要求出满足 \(i\in[l,r]\) 且 \(i\bmod k\in[x,y]\) 的所有 \(i\) 中，\(r_i\) 字典序最小的 \(i\)。若有多个这样的 \(i\)，答案为最小的那个 \(i\)。或报告无解。
\(|s|,|t|,q\le 10^5\)。
\(\text{2 s / 256 MB}\)。
本题做法大致由两个部分拼起来。
\(\bf{Part\space1}\) 排序
考虑将所有二元组 \((r_i,i)\) 按照题目要求排序。先将 \(s\) 和 \(t\) 拼接成一个大串 \(S\)。容易发现任意一个 \(r_i\) 就是 \(S\) 的 \(\mathcal{O}(1)\) 个子串拼接起来。
考虑比较字符串大小的方法，找到 \(\text{LCP}\) 然后比较下一位。那么我们就用 vector 存放一个字符串的所有段，用哈希进行字符串匹配，每次匹配到段端点。如果到段端点全部匹配，就进行下一段。否则比较失配位置的大小。
注意要多模，我使用了自然溢出和【】生日。
若两个字符串相同就比较 \(i\) 的大小。然后将上述过程重载为小于号，使用 stable_sort 进行排序。
时间复杂度为 \(\mathcal{O}(|s|\log |s|\log (|s|+|t|))\)，空间复杂度为 \(\mathcal{O}(|s|+|t|)\)。
\(\bf{Part\space 2}\) 回答询问
做完 \(\text{Part 1}\) 后，答案就是满足条件的 \(i\) 中排序后排名最小的那个。所以只需要求排名的最小值。
看到带 \(\bmod\) 的限制，考虑阈值分治。设阈值为 \(B\)。
-
\(k>B\)
我们令 \(i=uk+v\)。此时 \(0\le u\le \dfrac{|s|}{B}\)。枚举 \(u\)，就可以得到满足条件的 \(i\) 在 \(\mathcal{O}\left(\dfrac{|s|}{k}\right)\) 个区间内。用
ST表维护区间最小值，枚举这些区间进行查询。 -
\(k\le B\)
我们考虑对于每个 \(k\) 单独求解。此时 \(0\le i\bmod k<k\le B\)。即只会有 \(\mathcal{O}(B)\) 种余数。再对于每种余数 \(v\)，将 \(i\bmod k=v\) 的位置的排名按顺序放入一个数组，然后对这些数组维护
ST表。容易得知对于某个特定的余数，\([l,r]\) 内的位置 \(i\) 在新数组中的位置也是一个连续的区间。并且这些数组的总长度为 \(\mathcal{O}(|s|)\)。因为每一种余数只会有 \(\mathcal{O}\left(\dfrac{|s|}{k}\right)\) 个位置，乘以 \(k\) 就是 \(\mathcal{O}(s)\)。那么对于这些数组建立ST表的时间是 \(\mathcal{O}(|s|\log |s|)\)。然后遍历每一个询问，枚举 \([x,y]\) 中的每一个余数，此时枚举量为 \(\mathcal{O}(B)\)。然后得到在 \([l,r]\) 内的 \(i\) 在当前余数对应数组中的区间，查询区间最小值即可。
时间复杂度为 \(\mathcal{O}\left(\dfrac{q|s|}{B}+|s|B\log|s|+qB\log|s|\right)\)，空间复杂度为 \(\mathcal{O}(|s|\log |s|)\)。
取 \(B=\mathcal{O}\left(\sqrt{\dfrac{|s|}{\log |s|}}\right)\) 时，时间复杂度为 \(\mathcal{O}((q+|s|)\sqrt{|s|\log |s|})\)。
若把 ST 表换成四毛子，可以做到时间复杂度 \(\mathcal{O}((q+|s|)\sqrt{|s|})\)，但是没必要。
易知极限数据下瓶颈为 \(\text{Part 2}\)，这个时间复杂度可以接受。
标签：le,DNA,log,Arpa,复杂度,Mehrdad,dfrac,字符串,mathcal From： https://www.cnblogs.com/MnZnOIerLzy/p/18012606