[BOJ 12899]

문제 바로가기 : https://www.acmicpc.net/problem/12899
문제 설명은 위 링크에서 확인해주시길 바랍니다.

solution

review

조금 특이하다. 보통 원소의 개수를 입력받고 start, end를 정해준 후 업데이트를 진행하는데 여긴 end가 MAX다.
뭐 그것까진 그렇다치고 순서가 섞여있는 숫자들을 마구잡이로 들여와 업데이트하고 K번째를 출력해야 하기 때문에
숫자 그 자체를 입력받으면 세그먼트 트리를 합, 곱, 최댓값, 최솟값 … 등의 기준으로 설정해도 정렬하기 어렵다.
그래서 값으로 입력받지 말고 ‘인덱스’라고 생각하자. 값은 1을 증가시켜준다. (합 세그먼트 트리로 만들어야 한다)
그럼 리프노드에 값은 갱신되지만 인덱스로 들어가기 때문에 계속 무작위로 업데이트해도 정렬된 상태로 유지할 수 있다.

합 세그먼트 트리기 때문에 누적된 값과 K를 비교해가면서 최종적으로 K번째를 찾으면 된다.
루트는 업데이트 횟수만큼이기 때문에 K는 무조건 같거나 작을 수밖에 없다. 그의 자식들과 비교해가면서 내려가야 한다.
인덱스별로 값이 들어가 있기 때문에(정렬돼 있기 때문에) 왼쪽자식 노드가 K보다 작으면 왼쪽 서브트리는 모두 K번째보다 작다.
때문에 오른쪽 자식을 타고 내려가 해당 서브트리에서 같은 방식으로 K번째를 찾아나가면 된다.
오른쪽으로 타고 내려가게 되면 왼쪽 자식의 값만큼 빼야(idx - tree[node*2]) 위치가 보장된다.

ll query(int node, int start, int end, int idx) {
    if (start == end) return start;
    int mid = (start + end) / 2;
    if (idx <= tree[node * 2]) return query(node * 2, start, mid, idx);
    else return query(node * 2 + 1, mid + 1, end, idx-tree[node * 2]);
}