\begin{proof} We first consider $\Upsilon_1$.  We know that $\Upsilon_1$
will eventually be split into $O(k)$ pieces by calls to \csplitlr.  (A
single call to \csplitlr~might produce two splits of $\Upsilon_1$, if the
key being split on is a duplicate key.  But both of those splits are
counted in our $Block$ metric, so this is still within our work bound.) 
We can trace the path $P$ that those splits will take through
$\Upsilon_1$, and by Lemma \ref{lm:path} we know that $E[\,|P|\,]$ is
$\oklg$.  Now observe that, regardless of the order in which we perform
the splits, each node in the path will be used as a non-spinal node by
exactly one split.  (After a node is used as a non-spinal node, it becomes
a spinal node of whatever LRTreap it ends up in.)  If we denote the work
required for split $i$ by $N(i)$, then the total work required is: 

\begin{eqnarray*}
W    &  =  & \sumik N(i)
\end{eqnarray*}
\begin{eqnarray}
E[W] &  =  & E\left[\sumik N(i)\right]                  \\
     & \le & E\left[\sumik (2N_{ns}(i)+1))\right]
\end{eqnarray}
\vspace{-.2in}
\begin{eqnarray*}
     &  =  & 2E\left[\sumik N_{ns}\right]+k             \\
     &  =  & 2E[\,|P|\,]+k                      \\
     &  =  & \oklg
\end{eqnarray*}

where (2) follows from (1) and Lemma \ref{lm:cut} and the fact that all
the splits made by our algorithm are almost-unbiased.

An identical argument applies to $\Upsilon_2$.

To see that the joins are within our work bound, consider the final
product LRTreap $\Upsilon$ after all joins have been made, and imagine
reversing the join-order to split it back up into its component blocks. We
would first perform two splits to remove the root block from $\Upsilon$.
We would then recursively perform splits to remove the root blocks from
the two pieces of $\Upsilon$, and so on.  The splits made in this fashion
are determined only by the root of the component that is being split. Thus
these splits are almost-unbiased splits, so we can again apply the
argument above to see that the splits cost $\oklg$ expected work. But
joining two LRTreaps together takes the same amount of work as splitting
them apart, so $E[W_{joins}]=\oklg$ as well.

We still need to show that the costs of the trivial splits and joins made 
are within our work bound.  We define a ``trivial'' call to \cunion~
to be one in which either $\Upsilon_1$ or $\Upsilon_2$ is empty.  Observe
that such calls immediately return without generating any further calls, 
so the total number of such calls can be no more than twice the number of 
nontrivial calls.

Now, each nontrivial call that is made results in at least one nontrivial
join operation.  Our algorithm makes at most $2k$ nontrivial joins in all,
so there can be at most $2k$ nontrivial calls and $6k$ total calls.  No
call can contain more than a constant number of trivial splits and joins, 
so the work done on trivial splits and joins is $O(k)$.

Thus the total expected work required is $\oklg$. \end{proof}

