J. Splitstream

Main Observation

We never need to materialize any sequence.

If we know the length of every wire, then for a query $(x,k)$ we can walk backwards through the network until we reach the original input wire $1$.

Lengths of Wires

Let $\ell(w)$ be the length of wire $w$.

Split node.

If a split node reads input $x$ and writes outputs $y$ and $z$, then: \[ \ell(y)=\left\lceil\frac{\ell(x)}{2}\right\rceil, \qquad \ell(z)=\left\lfloor\frac{\ell(x)}{2}\right\rfloor. \]

Merge node.

If a merge node reads inputs $x$ and $y$ and writes output $z$, then: \[ \ell(z)=\ell(x)+\ell(y). \]

These values can be computed with memoized DFS because the network is acyclic.

Tracing One Query Backwards

Split Output

Suppose a split node takes input sequence \[ a_1,a_2,a_3,\dots \] Then:

• output 1 is \[ a_1,a_3,a_5,\dots \]

• output 2 is \[ a_2,a_4,a_6,\dots \]

• So:

• the $k$th element of output 1 is the $(2k-1)$th element of the input;

• the $k$th element of output 2 is the $(2k)$th element of the input.

Merge Output

Suppose a merge node takes sequences \[ a_1,a_2,\dots,a_p \qquad\text{and}\qquad b_1,b_2,\dots,b_q. \] Its output is \[ a_1,b_1,a_2,b_2,\dots \] until one sequence ends, and then the remaining elements of the longer sequence continue unchanged.

Therefore:

• while $k \le 2\min(p,q)$:

  • odd $k$ comes from the first input at index $(k+1)/2$;

  • even $k$ comes from the second input at index $k/2$.

  • after that, if $p>q$, the remaining elements come from the first input at index $k-q$;

  • if $q>p$, they come from the second input at index $k-p$.

  Algorithm

  1. Parse all nodes and record, for each output wire, which node created it.

  2. Compute wire lengths lazily with memoized DFS.

  3. For each query $(x,k)$:

     • if $k > \ell(x)$, print none;

     • otherwise repeatedly replace $(x,k)$ by the corresponding predecessor wire and predecessor index, using the rules above, until $x=1$.

     • On wire $1$, the sequence is simply $1,2,\dots,m$, so the answer is $k$ itself. enumerate

       Correctness Proof

       We prove that the algorithm answers every query correctly.

       Lemma 1.

       For every wire, the memoized formulas compute its correct length.

       Proof.

       The formulas follow directly from the definitions of split and merge nodes:

       • a split sends odd-positioned elements to one output and even-positioned elements to the other;

       • a merge outputs every element from both inputs exactly once.

       • Since the network is acyclic, recursively applying these formulas reaches the base wire $1$ and is well-defined. □

       Lemma 2.

       For a split node, the backward index transformation used by the algorithm is correct.

       Proof.

       By definition of the split operation, output 1 contains exactly the odd-indexed elements of the input, in the same order. So its $k$th element is input element $2k-1$. Likewise output 2 contains exactly the even-indexed input elements, so its $k$th element is input element $2k$. □

       Lemma 3.

       For a merge node, the backward index transformation used by the algorithm is correct.

       Proof.

       The merge node alternates elements from the two inputs as long as both still have elements. Therefore the first $2\min(p,q)$ output positions correspond exactly to alternating positions from the two inputs. After the shorter input is exhausted, the output continues with the remaining suffix of the longer input without any further mixing. The backward formulas are exactly these cases written explicitly. □

       Theorem.

       For every query $(x,k)$, the algorithm outputs the correct $k$th element of wire $x$, or none if that element does not exist.

       Proof.

       If $k > \ell(x)$, then wire $x$ has fewer than $k$ elements, so none is correct by Lemma 1.

       Otherwise, by repeatedly applying Lemmas 2 and 3, the algorithm transforms the query to an equivalent query on the predecessor wire of the current node. Because the network is acyclic, this process eventually reaches wire $1$. On wire $1$, the $k$th element is exactly $k$. Thus the returned value is the unique value that maps through the network to the original query position. □

       Complexity Analysis

       Let $N$ be the number of nodes and $Q$ the number of queries.

       Each wire length is computed at most once, so the total preprocessing is $O(N)$. Each query walks upward through at most one path in the DAG, so one query costs $O(N)$ in the worst case, which is easily fast enough for the given limits. Memory usage is $O(N)$.

       Implementation Notes

       • Wire lengths fit in 64-bit integers because no wire can contain more than the original $m$ values.

       • The answer on wire $1$ is just the queried index itself.