PS/Range Queries(2)
-
BOJ 13547 : 수열과 쿼리 5
https://www.acmicpc.net/problem/13547 13547번: 수열과 쿼리 5 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j: Ai, Ai+1, ..., Aj에 존재하는 서로 다른 수의 개수를 출력한다. www.acmicpc.net 이 문제는 Update 쿼리가 주어져 있지 않으므로 모스 알고리즘(Mo's Algorithm)으로 풀 수 있다. 처리 방법 : 수가 나오는 빈도를 저장할 배열을 정하여 각 쿼리에 대응 #include #define MEM 100007 #define sanic ios_base::sync_with_stdio(0) #define pb push_back using namespace std; t..
2020.08.05 -
BOJ 14504 : 수열과 쿼리 18
https://www.acmicpc.net/problem/14504 14504번: 수열과 쿼리 18 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다. 2 i k: Ai를 k로 www.acmicpc.net 우리는 이를 평방 분할(Sqrt Decomposition)로 풀 수 있다. 퀴리를 n^(1/2)만큼으로 분할 한 다음, 버킷에 정렬된 결과를 저장해놓으면 우리는 이를 lower_bound, upper_bound를 통해 k보다 크거나 같은 A_i의 인덱스를 찾을 수 있다. 그러므로 각 버킷에서 해는 n^(1/2)-(버킷에서 A_i> m..
2020.08.05