unordered_map이 PS하는 블로그

수열과 쿼리 3 문제는 머지 소트 트리를 이용해 해결할 수 있다. 아직 안 풀어봤다면 수열과 쿼리 3을 꼭 먼저 풀고, 수열과 쿼리 18에서 업데이트 쿼리를 어떻게 적용할 수 있을지 생각해보자. 여담으로, 이 문제는 수열과 쿼리 1.5와 완전히 같은 문제이다. 문제 요약 길이 10만 이하의 수열 A에서 다음 2가지 쿼리를 수행한다. 1 i j k : 구간 [i, j]에서 A의 원소 중 k보다 큰 것의 개수를 출력 2 i k : A[i]=k로 업데이트 사용 알고리즘 제곱근 분할법 풀이 k보다 큰 원소의 수를 lower_bound나 upper_bound를 이용하여 구하겠다는 발상까지는 머지 소트 트리와 같다. 하지만 업데이트 쿼리가 들어온다면 기존의 머지 소트 트리에서 O(logN)개의 정렬된 vector를..

수열과 쿼리 1과 정확히 같은 문제이지만 쿼리 정렬을 할 수 없다는 점만 다르다. 머지 소트 트리를 필수적으로 구현해야하는 문제이다. 수열과 쿼리 1을 머지 소트 트리로 풀었다면 그대로 제출하면 된다. 따라서 별도의 풀이는 적지 않고, 아래에 수열과 쿼리 1 풀이 링크를 걸어두겠다. 아직 수열과 쿼리 1을 풀지 못했다면 쿼리 정렬을 사용해서는 어떻게 풀 수 있는지 고민해보기 바란다. 수열과 쿼리 1 풀이링크 https://unorderedmap.tistory.com/23 수열과 쿼리 1 [BOJ 13537] 수쿼 시리즈의 화려한 도약을 알리는 매우 재미있는 문제이다. 머지 소트 트리 기본 문제이면서도, 이 문제는 머지 소트 트리 외에 별해가 존재한다. 개인적으로 별해의 아이디어가 상당히 의미 unorde..

수쿼 시리즈의 화려한 도약을 알리는 매우 재미있는 문제이다. 머지 소트 트리 기본 문제이면서도, 이 문제는 머지 소트 트리 외에 별해가 존재한다. 개인적으로 별해의 아이디어가 상당히 의미 있다고 생각한다. 아래 풀이에 별해와 관련된 내용은 모두 가려놓았으니, 최소 30분 정도는 별해에 대해 고민해보는 것을 추천한다. ** 수열과 쿼리 3 풀다가 오신 분들은 머지 소트 트리에 대한 풀이인 풀이 1만 읽으면 수열과 쿼리 3을 풀 수 있다. 문제 요약 길이 10만 이하의 수열 A에서 다음 쿼리를 수행한다. i j k : 구간 [i, j]에서 k보다 큰 원소의 수를 출력한다. 사용 알고리즘 풀이 1) 머지 소트 트리 풀이 2) Hint : 오프라인 쿼리라는 점을 이용 더보기 스위핑 + 세그먼트 트리 풀이 풀이 ..