We can solve this problem efficiently using a persistent Weighted Balanced Leafy Tree (WBLT).

Specifically, the WBLT maintains a binary sequence (0s and 1s), where each leaf node stores a single bit (0 or 1). Let \(T_{i+1}\) denote the root of the WBLT corresponding to version \(i\). To construct \(S_{i+1}\) by concatenating \(S_{L_i}\) and \(S_{R_i}\), we merge the subtrees of \(T_{L_i}\) and \(T_{R_i}\), assigning \(T_{i+1}\) as the new root. To minimize query time, if the size of \(S_{L_i}\)’s subtree exceeds the limit (\(10^{18}\)), we directly assign \(T_{i+1} = T_{L_i}\) (skipping unnecessary merges).

To query the \(p\)-th character in \(S_{i+1}\), we perform a binary search on the WBLT, analogous to Binary Search on Segment Tree.

Each merge operation requires \(O(\log V)\) time and space complexity, while queries run in \(O(\log V)\) time, where \(V=10^{18}\) is the maximum tree size.

Therefore, this solution achieves \(O(Q \log V)\) time and space complexity, which runs fast in practice and can be easy to code.

This solution may be advanced for beginners, but I personally believe it’s easier to think.