offline query
-
[BOJ] 16978 수열과 쿼리 22PS/BOJ 2020. 8. 24. 20:32
https://www.acmicpc.net/problem/16978 16978번: 수열과 쿼리 22 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v: Ai = v로 변경한다. 2 k i j: k번째 1번 쿼리까지 적용되었을 때, Ai, Ai+1, ..., Aj의 합을 출력한다. www.acmicpc.net 알고리즘: Segment tree, Offline query 시간복잡도: $O((N+M)logN+MlogM)$ 접근: 2번 쿼리를 보면, 'k번째 1번 쿼리까지 적용되었을 때' 라는 문구를 볼 수 있다. 이걸 보면 쿼리들을 k 순서로 정렬하는 offline query를 쓰면 되겠구나 라고 생각할 수 있다. 쿼리들을 k에 대한 오름..
-
[BOJ] 13537 수열과 쿼리 1PS/BOJ 2020. 8. 23. 23:15
https://www.acmicpc.net/problem/13537 13537번: 수열과 쿼리 1 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다. www.acmicpc.net 알고리즘: Segment tree, Offline query 시간복잡도: $O((N+M)logN+MlogM)$ 접근: 1. 구간 쿼리 및 많은 쿼리 개수 : Segment tree 2. $A_i$의 값을 변경하는 쿼리가 없다 -> $A_i$에 대한 정보를 segment tree에 한번 넣어주고 나면, 그 뒤에는 $A_i$에 대해 신경 쓸 필요가 없다. 3. 쿼리의..