Given two strings $$$s,t$$$, write $$$r_i$$$ for the string obtained by inserting $$$t$$$ into $$$s_i$$$ and $$$s_{i+1}$$$. If $$$i=0$$$, insert at the beginning, if $$$i=|s|$$$, insert at the end.
Formally, $$$r_i=\overline{s_1\dots s_it_1\dots t_{|t|}s_{i+1}\dots s_{|s|}}$$$.
There are $$$q$$$ queries, each of which gives $$$l,r,k,x,y$$$. You need to find the $$$i$$$ with the smallest $$$r_i$$$ dictionary order among all $$$i$$$ satisfying $$$i\in[l,r]$$$ and $$$i\bmod k\in[x,y]$$$. If there is more than one such $$$i$$$, the answer is the smallest $$$i$$$. Or report no solution.
$$$|s|,|t|,q\le 10^5$$$.
$$$\text{2 s / 256 MB}$$$.
The approach to this problem is roughly put together in two parts.
$$$\bf{Part\space1}$$$ Sorting.
Consider sorting all the binary groups $$$(r_i,i)$$$ as required by the question. First splice $$$s$$$ and $$$t$$$ into a large string $$$S$$$. It is easy to see that any $$$r_i$$$ is the $$$\mathcal{O}(1)$$$ substring of $$$S$$$ stitched together.
Consider the method of comparing string sizes by finding $$$\text{LCP}$$$ and comparing the next bit. Then we use a vector to store all the segments of a string, and match the string with a hash, one at a time, up to the segment endpoint. If they all match up to the end of the segment, then we move on to the next segment. Otherwise, compare the size of the mismatched positions.
Note that to multimode, I used the natural overflow and [] birthday.
If two strings are the same compare the size of $$$i$$$. The above procedure is then overloaded to less than and sorted using stable_sort.
The time complexity is $$$\mathcal{O}(|s|\log |s|\log (|s|+|t|))$$$ and the space complexity is $$$\mathcal{O}(|s|+|t|)$$$.
**$$$\bf{Part\space 2}$$$ Answer the query **
After doing $$$\text{Part 1}$$$, the answer is the one with the smallest rank after sorting among the $$$i$$$ satisfying the condition. So only the smallest value of the ranking is required.
Seeing the restriction with $$$\bmod$$$, consider threshold partitioning. Let the threshold be $$$B$$$.
- $$$k>B$$$.
We make $$$i=uk+v$$$. At this point $$$0\le u\le \dfrac{|s|}{B}$$$. Enumerating $$$u$$$ gives us $$$i$$$ that satisfies the condition within $$$\mathcal{O}\left(\dfrac{|s|}{k}\right)$$$ intervals. Enumerate these intervals for querying, using the ST table to maintain interval minima.
- $$$k\le B$$$
We consider solving for each $$$k$$$ individually. At this point $$$0\le i\bmod k<k\le B$$$. That is, there will only be $$$\mathcal{O}(B)$$$ remainders. Then for each remainder $$$v$$$, the rankings of the positions where $$$i\bmod k=v$$$ are placed in order in an array, and the ST table is maintained for these arrays. It is easy to see that for a particular remainder, the position $$$i$$$ within $$$[l,r]$$$ is also a continuous interval in the new array. And the total length of these arrays is $$$\mathcal{O}(|s|)$$$. Since there will only be $$$\mathcal{O}\left(\dfrac{|s|}{k}\right)$$$ positions for each kind of remainder, multiplying by $$$k$$$ is $$$\mathcal{O}(s)$$$. Then the time to build the ST table for these arrays is $$$\mathcal{O}(|s|\log |s|)$$$.
Then iterate through each query, enumerating each remainder in $$$[x,y]$$$, at which point the enumeration is $$$\mathcal{O}(B)$$$. Then get the interval of $$$i$$$ in $$$[l,r]$$$ in the array corresponding to the current remainder, and query the interval minimum.
The time complexity is $$$\mathcal{O}\left(\dfrac{q|s|}{B}+|s|B\log|s|+qB\log|s|\right)$$$ and the space complexity is $$$\mathcal{O}(|s|\log |s|)$$$.
The time complexity is $$$\mathcal{O}\left((q+|s|)\sqrt{\dfrac{|s|}{\log |s|}}\right)$$$ when $$$B=\mathcal{O}\left(\sqrt{\dfrac{|s|}{\log |s|}}\right)$$$ is taken.
If the ST table is replaced with the method of four Russians, the time complexity $$$\mathcal{O}\left((q+|s|)\sqrt{|s|\log |s|}\right)$$$ can be achieved, but it is not necessary.
The bottleneck under easy-to-know limit data is $$$\text{Part 2}$$$, which is an acceptable time complexity.
