merge sort tree (5) 썸네일형 리스트형 백준 2912 - 백설공주와 난쟁이 https://www.acmicpc.net/problem/2912 필요 지식 이 포스트에서는 머지 소트 트리를 사용하며 약간의 수학적 통찰력이 필요하다. 모스 알고리즘 같은 다른 풀이는 다루지 않는다. 아이디어 A번째 난쟁이와 B번째 난쟁이까지를 하나의 구간으로 보자. 그러면 이 구간에서 절반을 초과하는 색깔(이하 과반수)이 존재하는지 구해야 한다. 구간에서 어떤 원소 하나를 선택한다고 해보자. 이 색깔이 과반수일 확률은 $\frac{1 + \epsilon}{2}$이라는 것은 바로 이해할 수 있다. 반대로 과반수가 아닐 확률은 $\frac{1 - \epsilon}{2}$가 된다는 뜻이다. 그러면 원소를 r번 선택했을 때 과반수가 아닐 확률은 $(\frac{1 - \epsilon}{2})^{r}$가 된다... 백준 13537 - 수열과 쿼리 1 https://www.acmicpc.net/problem/13537 힌트 1 더보기 수열의 원소를 바꾸는 연산은 없다. 힌트 2 더보기 수열의 갱신이 없는 상태에서 특정 구간의 원소 index를 빠르게 찾기 위해 Merge Sort Tree를 이용할 수 있다. 풀이 수열이 주어지고 특정 구간에서 k보다 큰 원소를 찾는 연산을 최대 10만 번 수행한다. 따라서 해당 연산을 빠르게 수행할 필요가 있고, Merge Sort Tree가 이를 가능케 한다. 머지 소트 트리를 구현해서 k보다 큰 원소가 나타나는 index를 upper bound로 찾으면 특정 구간에서 k 이하 원소의 개수를 확보할 수 있다. 우리는 k보다 큰 원소의 갯수를 알고 싶으므로 (구간의 길이 - 머지 소트 트리의 질의로 찾은 k 이하 원소.. 백준 13544 - 수열과 쿼리 3 https://www.acmicpc.net/problem/13544 특정 구간에서 어떤 원소를 상대로 질의를 처리하는 것은 머지 소트 트리를 이용하여 할 수 있다. 머지 소트 트리를 구현한 후 문제에서 요구하는 대로 질의를 처리한 결과를 출력하면 AC를 받을 수 있다. 마지막으로 출력한 결과와 XOR 연산을 해줘야 하는 것을 잊지 말자. # XOR를 해주는 이유는 오프라인 쿼리를 사용할 수 없게 하기 위함이라고 한다. 전체 코드 더보기 #include using namespace std; vector tree[400000]; int ar[100001]; int mid(int s, int e) { return s + (e - s) / 2; } void init(int node, int start, int .. 머지 소트 트리 Merge Sort Tree 머지 소트 트리는 세그먼트 트리의 파생형으로 위 그림처럼 각 node가 정렬된 구간을 보유하는 형태로 되어있다. 머지 소트 트리는 세그먼트 트리와 유사하게 구현할 수 있다. 초기화 void set_mst(int node, int start, int end) { vector &cur = mst[node]; if (start == end) { cur.push_back(ar[start]); return; } int m = mid(start, end); set_mst(node * 2, start, m); set_mst(node * 2 + 1, m + 1, end); vector &l = mst[node * 2], &r = mst[node * 2 + 1]; cur.resize(l.size() + r.size()).. [ICPC] 백준 7469 - K번째 수 https://www.acmicpc.net/problem/7469 수열의 부분 구간에서 연산을 하는 것은 머지 소트 트리로 처리할 수 있다. 머지 소트 트리를 구현한 후 이진 탐색을 이용하여 구간의 k번째 원소를 찾아주면 된다. 전체 코드 - query 함수에서 lower_bound를 사용했으므로 kth - 1을 pivot으로 삼은 것에 유의하라. 더보기 #include using namespace std; int n, m; vector mst[400000]; int ar[100001]; inline int mid(int s, int e) { return s + (e - s) / 2; } void set_mst(int node, int start, int end) { vector &cur = mst[no.. 이전 1 다음
