Imagine a weighted directed acyclic graph of \(Q + 2\) nodes numbered \(0\) to \(Q+1\). Nodes \(0\) and \(1\) are the terminal nodes, while all other nodes have a “left parent” and “right parent”, with the edge to the left-parent having a weight of \(0\) and the edge to the right-parent having a weight of the length of the left-parent’s string.

There is a naive \(O(Q^2)\) solution where to answer a query, you climb one of the parents corresponding to which one contains the index \(X_i\), then you shift the index accordingly, until you reach a terminal node.

How do we optimize this? We might think of binary lifting, but it’s hard to do this with two “parents” rather than one. It turns out to not be productive to think of the left-parent or the right-parent; instead, consider the parent with the shorter string to be the “light parent”, while the other to be the “heavy parent” (and use the edge weight to distinguish left and right, since the left-parent always has the edge weight of \(0\)). Therefore, if we travel through the edge to the light parent, the string must be at most half the previous length, otherwise we can use binary lifting to optimize climbing the chain of heavy parents. (Quick summary: for each node, store the result and weight-sum of climbing \(1, 2, 4, 8, ..., 2^x\) heavy edges. To binary lift, use the information of the weight sums and the string lengths to determine if the sought index is within that string)

There is one caveat, in that the string lengths could blow up exponentially. We will have to cap the “known string length” to some length \(M \ge \max_i X_i\) to prevent overflows, but this seems to break our reasoning as to light-parents and heavy-parents. To fix this, we define the heavy-parent to tie-break in favor of the left-parent, since that would be where we’d want to climb to if both parents have capped lengths. This ensures that the first time we traverse to a light-parent, the string length must then become \(< M\).

Thus, for each query, we may traverse up to \(O(\log M)\) light edges, and in between, binary lifting the chain of heavy edges could take up to \(O(\log Q)\) time each, therefore the problem is solved in \(O(Q \cdot \log M \cdot \log Q)\) time.