Finding all pairs of points with no point in between
If you can select $p_j$ in $O(n)$ time such that it's part of the middlemost group of elements with the same color, the following algorithm works. However I haven't found such a prerequisite.
After finding $p_j$ we can do an $O(n)$ scan to find $p_k$, the minimal element $&gt;p_j$ with the opposite color. We can do a similar scan for $p_i$, the maximal element $&lt;p_j$ with the opposite color. Finally we can partition our array in $O(n)$ time into three subarrays, left ($\{\leq p_i\})$, middle (rest, all with same color as $p_j$), and right ($\{\geq p_k\}$).
In an analysis similar to quicksort you can prove that if we recursively apply the above partitioning to the left and right subarrays we end up with a call tree that has height $\log k$ and at each level of the tree we do a combined $O(n)$ operations, thus a total runtime of $O(n \log k)$.
Afterwards (or during) you can simply iterate over each adjacent partition and output the opposite colored pairs (because each partition is uniformly colored).