We solve it by binary searching.
We decide whether the median can be made \(X\) or greater.
After the \(M\) operations, there are \(N+M\) sticks, so it is sufficient to have at least \(\frac{N+M+1}{2}\) sticks of length \(X\) or greater in the final state.
Consider repeatedly splitting a stick of length \((2X-1)\) or greater as many times as possible. When no more repetition can be done, if there are strictly less than \(\frac{N+M+1}{2}\) sticks of length \(X\) or greater, then the median cannot be made \(X\) or greater.
Suppose that there are \(\frac{N+M+1}{2}\) or more such sticks. Let \(S\) be the total length of the shortest \(\frac{N+M+1}{2}\) sticks among them.
Then we see that the total length of the sticks of length \(X\) or greater is \(S\) or greater.
The sum of lengths of the other sticks is \(\sum_{i=1}^{N}{A_i}-S\). To have \(\frac{N+M-1}{2}\) or more such sticks, it is necessary that \(\frac{N+M-1}{2} \leq \sum_{i=1}^{N}{A_i}-S\).
Conversely, suppose that this inequality holds.
If you repeatedly split a stick of length \((2X-1)\) or greater as many times as possible, keep the \(\frac{N+M+1}{2}\) shortest sticks, and perform the operation as many times as possible for the others, you will perform the operation \(\frac{N+M+1}{2}+\sum_{i=1}^{N}{A_i}-S-N\) times. This is greater than or equal to \(\frac{N+M+1}{2}+\frac{N+M-1}{2}-N=M\), so the operation can be done exactly \(M\) times.

Naively splitting sticks of length \((2X-1)\) or greater costs a tremendous computational complexity.
However, when you repeatedly split a stick of length \(A_i\), the possible resulting lengths are \(\frac{A_i}{2^0},\frac{A_i}{2^1},\dots\), and these values plus one, so there are \(O(\log \max(A))\) possible distinct lengths. By tracking the number of sticks of each length, the process can be simulated in \(O(\log {\max(A)})\) time.

Also, starting from one stick, if you repeatedly split a piece of length \((2X-1)\) or greater as many times as possible, the resulting sticks will have at most three distinct lengths. Thus, for \(i=1,2,\dots,N\), when splitting \(i\) sticks, the resulting sticks will have at most \(O(N)\) distinct lengths, and sorting them can be done in \(O(N\log N)\).

The total complexity is \(O(N(\log{ \max(A)})^2+N\log{N}\log{\max(A)})\).

Bonus: solve it in \(O(N\log{\max(A)})\) time.