AtcoderをしていてC++のsetで二分探索をしたときにvectorを同じ書き方をしてTLEになる罠

vectorと同じ書き方だとO(N)になる

Nをsetの要素数とします。
下のコードのようにvectorと同じ書き方で書くと、「二分探索なのでO(log N)」と思いきや「O(N)」になります。

C++17

#include <bits/stdc++.h>
using namespace std;
int main(){
  set<int>st;
  st.insert(1);
  st.insert(3);
  int a = 2;//a以上で最小の値を見つけたい
  auto it = lower_bound(st.begin(),st.end(),a);
  cout<< *it <endl;
}

3

原因はsetではランダムアクセスができないから(らしい)です。vectorの場合[ i ]や.at( i )などでランダムアクセスができますが、setではできません。なので「setの中身を最初から順番に見ていく」のようなことが起きてO(N)になると思われます。

set専用の二分探索の書き方をすればO(log N)になる

C++17

#include <bits/stdc++.h>
using namespace std;
int main(){
  set<int>st;
  st.insert(1);
  st.insert(3);
  int a = 2;//a以上で最小の値を見つけたい
  auto it =st.lower_bound(a);
  cout<< *it <<endl;
}

3

「set.lower_bound(p)」のように書けばO(log N)で、p以上で最小の値を取得することができます。もちろんupper_boundも同じように使えます。
set専用のかき方をすることによって、setの木構造を根から調べていくことにより、O(log N)になっていると思われます。詳しい仕組みは緑コーダーにはわかりません()

おわりに

setでvectorと同じ書き方をするとTLEになるという記事を1つ見つけましたが、「実行時間が長くなる」のようなことだけ書かれていて、「TLEになる原因」のような記事がなかったのでこの記事を書きました。これを知るきっかけになった問題を貼っておきます。よければ解いてみてください。
https://atcoder.jp/contests/abc260/tasks/abc260_d