해답은 세그트리라고 알지만, 맵으로 해결할 수 있는 방법이 없나 싶어 이야기를 남깁니다.

현재 들어온 값이 맵의 end() -1에 존재하면 끝에 위치하는거니 1등이 될 가능헛ㅇ이 있는 것이고, 그게 아닌 모든 값들은 맵에서 몇번째에 위치하는지 order를 구해주면 된다고 생각했습니다.

그런데 order 구하는 방법이 logN에 끝날 줄 알았는데 그게 안되더라구요.

vector에서는 lower_bound() - V.begin()을 하면 인덱스가 나타나지만 map은 균형 이진 트리라 인덱스 개념이 없다보니 안되는 것 같더라구요

이런 생각에 대해 조언을 좀 구하고싶습니다.