\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{amsmath, amsfonts}
\usepackage{clrscode}

\begin{document}

\begin{center} \Large 
{\scshape 6.897 Advanced Data Structures (Spring'05)} \\[1ex]
{Prof.~Erik Demaine \quad\quad TA: Mihai P\v{a}tra\c{s}cu} \\[2ex]
\framebox{Problem 9 -- Solution}
\end{center}

\paragraph{1.}
If we find two consecutive points of the same color, we can eliminate
the second one, and the result of any predecessor query will not
change. Thus, we can assume colors alternate in the sorted list of
points. By symmetry, assume the first point is red. For every $i$,
create a segment between the $2i$-th and $(2i+1)$-st points (observe
that the segments are disjoint). Now, if $x$ stabs a segment, it's
predecessor has an even index, so it is blue. Otherwise, the
predecessor is red.

\paragraph{2.}
Replace a segment $[a,b]$ by the point $(a, u-b)$ in two dimensions.
Now, for some $x$, we query the range $[0,x] \times [0, u-x]$. We have
$(a, u-b) \in [0,x] \times [0, u-x] \iff a \le x, u-b \le u-x \iff a
\le x \le b \iff x \in [a,b]$.

\paragraph{3.}
In the preprocessing phase, compute the Euler tour traversal of the
tree. For each node, remember the index of the first and last
appearance of the node. Leaves appear only once. To mark a node, we
insert a segment whose endpoints are the indices of the first and last
appearance in the Euler tour. To unmark a node, we delete that
segment. To query a leaf $v$, do a segment stabbing query at the
(unique) point where $v$ appears in the Euler tour. A marked ancestor
is equivalent to a segment beginning before $v$'s appearance, and
ending after it (by definition of the Euler tour). Thus, $v$'s
associated point stabs the segment associated to any marked ancestor.

\end{document}
