머지소트트리2 BOJ 7469 - K번째 수 ( 머지소트트리, pst ) https://www.acmicpc.net/problem/7469 두가지 방법으로 가능 머지소트트리, 퍼시스턴트세그트리 pst론 구간 k번째 수를 효과적으로 셀 수 있다. (세그먼트트리에서 전체 k번째 수를 세는 것이랑 비슷함) 최대 1e5개의 정수 배열이 주어진다. 배열의 원소는 절대값이 1e9보다 작은 정수이다. 다음 쿼리를 처리 s,e,k : 구간[s,e]의 k번째 수를 출력 - 머지소트트리 머지소트트리를 만든 후, 1. 쿼리마다 -1e9~1e9사이에서 k번째 수가 될 수 있는 최소값을 구한다. 구간에서 x미만의 수의 개수가 k-1개이상인 수 중 최소값을 구해주면 된다. (이분탐색 시 음수범위에 주의) 2. 구간에서 x이상 최소값을 찾아 출력해준다. const int MAX = 2e5 + 4; co.. 2020. 6. 10. BOJ 15899 - 트리의 색깔 (ett, 머지소트트리) https://www.acmicpc.net/problem/15899 기록용 최대 2e5개의 정점을 갖는 트리가 주어진다. 각 정점마다 최대 2e5의 값(색)을 하나씩 갖는다. 다음 쿼리를 처리하자 v c : 정점v를 루트로 하는 서브트리에서 값이 c이하인 정점의 수 서브트리를 구간트리로 처리할 수 있는지? 할 수 있다면 머지소트트리가 가장 적합함 (update쿼리가 없어서 가능) ett번호를 붙여주고 머지소트트리 일반적인 풀이 쓰면 된다. const int MAX = 2e5 + 4; const int MOD = 1e9 + 7; const int SMAX = (1 = 1; i--) { seg[i] = seg[i * 2 + 1]; seg[i].insert(seg[i].end(), seg[i * 2].begi.. 2020. 6. 2. 이전 1 다음