共著 : miroqqwy

GCC拡張である #include に含まれる tree を用いることで、set のように要素をソートした状態で管理しつつ、find_by_order により k 番目の要素へ \( O(\log N) \) でアクセスできるデータ構造を扱うことができます。

この構造では、要素の挿入および k 番目の要素へのアクセスはいずれも \( O(\log N)\) で行えるため、クエリ数を \(Q\) とすると、全体の計算量は \( O(Q \log Q) \) となり、十分高速にこの問題を解くことが出来ます。

ただし、tree は set と同様に要素の重複を許さないため、重複を扱う場合には pair<値, id> のように一意な識別子を付加して管理する必要があります（このとき、id は出力には影響しない補助的な値です）。

実装例