属する区間(メモ書き) - モラトリアムライフ

互いに素な区間 $I_k$ $(k = 0, 1, 2, ..., n-1)$ (つまり, $i \neq j \Longrightarrow I_i \cap I_j = \emptyset$ )に関して
$\displaystyle{U := \bigcup_{0 \leq k ＜ n}^{} I_k}$ 上の点 $x \in U$ が属する区間 $I_m$ を( $O(\log n)$ のオーダーで)求めるには,
std::set に pair<int, int>で区間を保持しておいて, make_pair( $x$ のindex, INF)を"upper_bound"メソッドで探して得られるイテレータを1つ前に戻せば良い

入力から区間が変わらない静的な場合は, std::vectorをソートしたものを二分探索を行なっても良い(メモリ効率自体はこちらの方が良い)