수열과 쿼리 1.5 [BOJ 17410] 수열과 쿼리 18과 완전히 같은 문제이다. 아래 링크에는 수열과 쿼리 18에 대한 설명이 있다. https://unorderedmap.tistory.com/27 수열과 쿼리 18 [BOJ 14504] 수열과 쿼리 3 문제는 머지 소트 트리를 이용해 해결할 수 있다. 아직 안 풀어봤다면 수열과 쿼리 3을 꼭 먼저 풀고, 수열과 쿼리 18에서 업데이트 쿼리를 어떻게 적용할 수 있을지 생각해보자. 여 unorderedmap.tistory.com 문제 풀이 2022.02.19
수열과 쿼리 18 [BOJ 14504] 수열과 쿼리 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를.. 문제 풀이 2022.02.16