[BOJ] 16978 수열과 쿼리 22

PS/BOJ 2020. 8. 24. 20:32

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에 대한 오름차순으로 정렬하여서,

1번 쿼리 처리 -> $k\le 1$인 2번 쿼리 모두 처리 -> 2번 쿼리 처리 -> $k\le 2$인 2번 쿼리 모두 처리 -> ...

이렇게 순서대로 처리해주면 각 쿼리마다 $O(logN)$만에 처리해줄 수 있다.

코딩 코딩