title: Merging search trees and finding elements in them
body: <p>I've got this problem in my theoretical homework on algorithms and data structures related to search trees:</p>
  <p>Given <em>n</em> numbers <em>a</em><sub>1</sub>, ..., <em>a</em><sub>n</sub>, initially each in its own set. There are two types of queries:</p>
  <ol>
  <li>unite two sets;</li>
  <li>find the smallest element bigger than <em>x</em> in a specific set.</li>
  </ol>
  <p>In these queries, set is specified by one of its elements' index in <em>{a<sub>i</sub>}</em>. The task is to process <em>q</em> queries in <em>O(n + q log(n))</em> time.</p>
  <p>I've tried using AVL trees to store sets' elements, but this approach results in <em>O(n log(n))</em> or <em>O(n)</em> merge time, so the overall time complexity requirement is not satisfied. At the moment I have only these few ideas (but actually they don't quite help):</p>
  <ol>
  <li>There are at most <em>n</em> unite queries.</li>
  <li>If <em>q &gt; n</em>, eventually, we'll need to build a search tree containing all <em>n</em> elements of <em>{a<sub>i</sub>}</em> to process the last <em>(q - n)</em> queries of type <em>(2)</em>. Thus, it seems to be reasonable to first solve the problem with <em>q ≤ n</em> and then naturally extend the solution to <em>q &gt; n</em>.</li>
  <li>To create a set containing <em>(k + 1)</em> elements at least <em>k</em> merge operations is needed (this is easy to prove by mathematical induction), so at each step of processing queries we need work with &quot;not-so-big&quot; sets only. This might yield some tight asymptotic estimates.</li>
  <li>Probably there is a way to somehow scan several first queries before processing them, understand which sets are involved in type <em>(2)</em> queries, and merge them only, ignoring other unite requests.</li>
  <li>There is no memory limit, so this might be abused in some way.</li>
  </ol>