\((P_i, T_i, R_i)\) はこれらをキーに降順にソートしておく.
ある \(T_i\) の数値を持つ店の中での最大の \(R_i\) を管理するセグメント木を用意する.
店をひとつずつ取り出した時点で \(P_i\) については以前取り出した店よりは小さいことは確実なので \(P_i\) は見なくてもいい.
\(T_i\) より大きい範囲での \(R_i\) の最大値をセグメント木に問い合わせ, これが \(R_i\) より大きければ今取り出した店は下位互換である.
そうでなければ, セグメント木に今取り出した店の情報を登録する.