Merge sort tree
-
[BOJ] 13547 수열과 쿼리 5PS/BOJ 2020. 8. 31. 00:34
https://www.acmicpc.net/problem/13547 13547번: 수열과 쿼리 5 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j: Ai, Ai+1, ..., Aj에 존재하는 서로 다른 수의 개수를 출력한다. www.acmicpc.net 알고리즘: Merge sort tree 시간복잡도: $O(NlogN+Mlog^2N)$ 접근: [l, r] 구간에 속하는 $A_i$ 중 서로 다른 수의 개수를 구하는 문제이다. 매 쿼리마다 [l, r] 을 모두 살펴보면 $O(MN)$으로 TLE를 받게 된다. 따라서, 어떻게 하면 중복되는 $A_i$들의 값을 걸러낼 수 있을지 생각해봐야한다. 당연히 $A_i$의 값 그대로 세그먼트 트리에 ..
-
[BOJ] 수열과 쿼리 3PS/BOJ 2020. 8. 23. 23:36
https://www.acmicpc.net/problem/13544 13544번: 수열과 쿼리 3 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다. www.acmicpc.net 알고리즘: Merge sort tree 시간 복잡도: $O(NlogN+Mlog^2N)$ 얼핏 봤을 때는 수열과 쿼리 1과 동일한 문제인 것 같지만 이전 쿼리의 결과 값으로 쿼리를 만들어야 한다. l = a^last_ans r = b^last_ans k = c^last_ans 처럼 (a, b, c)가 입력으로 주어지면 이전 결과 값과 XOR을 하여 (l, r, k)..