online query
-
[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)..