はじめに結論

Pythonのsetは集合の管理ができますが、要素にindexを持っていないので「小さい方からx番目の要素を出力する」という操作を要素数 N に対して $O(N)$ でしか行えません。

あ〜遅すぎる。

結論を言うと、Binary Indexed Treeと二分探索で$O((logN)^2)$になります。もっと高速化できるかはよく知りません。

Salmonize氏、joe氏ご指摘ありがとうございました。
$O((logN)^2)$としていますが、BIT上の二分探索を応用することで二分探索パートがBITのクエリ処理を必要としなくなり、$O(logN)$に高速化されます。

どんな理屈？

Binary Indexed Tree(以下BIT)を用意しましょう。なに？BITを知らない？
https://ja.wikipedia.org/wiki/フェニック木

xを集合に追加する場合、BITのx番目の要素に+1するということにしましょう。
例えば、{3, 1, 4}の集合を作りたい！と思ったら、

BIT配列の3番目の要素に+1
BIT配列の1番目の要素に+1
BIT配列の4番目の要素に+1

これでOKです。

ではlower_boundを考えていきましょう。二分探索します。小さい方からx番目の要素が欲しい時、

「y以下の要素がx個以上あるか？」という判定を使って二分探索すると、BITでy以下の要素の個数は$O(logN)$でわかり、

さらに二分探索自体に$O(logN)$かかるので

合計$O((logN)^2)$です。なるほどね。

floatやstrを扱いたい場合は工夫が必要です。floatだったら元々の数を定数倍しておけばよし、strは文字コードを使えばいいですが実用的には見えません。

また動的な変更に思ったより強くないのでオンラインクエリに弱いかもしれません。
でかい数を格納する際も座標圧縮などをしないとうまくいきません。

まあsetで順序集合を考えるよりは速いかなあ...
平衡二分探索木の方が便利そう（終了）

そういえばコード書いてないですね。