pbds1 [백준 1168] 요세푸스 문제 2 (Platinum III) (Feat. PBDS) - 세그먼트 트리 없이 풀기 https://www.acmicpc.net/problem/1168 1168번: 요세푸스 문제 2 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 100,000) www.acmicpc.net 컴퓨터공학과에서 를 수강한 학생들이라면 std::set이 레드-블랙 트리로 구현되어 있다는 것을 알 것이다. 레드-블랙 트리는 Binary Search Tree다. 즉 원소들이 나름의 순서를 갖추고 정렬되어 있다는 것이다. 정렬되어 있다는 것은, 마치 Binary Search 하듯이 k번째 원소를 O(logn) 안에 접근할 수 있음을 함의한다. 그러나 그것을 하기 위해서는 rb-tree의 각 노드들이 subtree의 개수를 저장하고 있어야 한다. std::set은 이 기능을 제공하.. 2022. 8. 17. 이전 1 다음
