말씀하신 알고리즘은 이분 탐색입니다. 정렬된 배열에서 어떤 원소가 들어가야 할 위치를 찾는 알고리즘입니다. C++ STL에는 lower_bound(), upper_bound() 등이 구현되어 있습니다.

만약 이분탐색이라면 위 문제에서 1넣고 정렬하고 5넣고 정렬하고 2넣고 정렬하고 이렇게 매 삽입시마다 정렬을 수행해야 할까요?

그렇게 된다면 N * NlogN이 될거 같은데.. 

말씀하신대로 그냥 정렬된 배열로 둔다고 치면 이분탐색으로 위치를 O(lgN)에 찾을 수 있으나 삽입을 할 때 중간에 원소를 넣어야하니 O(N)이 걸려 총 O((N+lgN)*N) = O(N^2)입니다.(N^2보다 NlgN이 작으니 NlgN은 무시)

1. "현재 그룹에 있는 원소 중에 특정 원소 x가 몇 번째로 큰지를 확인하는 연산", "집합에 원소를 대입하는 연산"을 모두 O(lgN)에 수행해주는 Binary Search Tree(+self balancing)를 직접 구현하기(JAVA에는 애초에 BST 라이브러리가 없는걸로 알고 C++의 map/set은 "현재 그룹에 있는 원소 중에 특정 원소 x가 몇 번째로 큰지를 확인하는 연산"을 O(lgN)에 지원하지 않아 결국 직접 구현해야 합니다.)

2. 세그먼트 트리를 활용하기

3. 1번에서 소개한 BST를 직접 구현할 필요 없이 gcc Policy-Based Data Structures를 이용하기

이 3가지 방법이 있습니다.

세그먼트 트리는 개념이 다소 난이도가 있는 반면 구현은 간단합니다. BST는 개념이 그렇게 어렵지는 않지만 구현이 꽤 어렵습니다. 일반적으로 비슷한 문제를 세그먼트 트리로 많이 풀곤 합니다.