https://www.acmicpc.net/problem/18436
18436번: 수열과 쿼리 37
길이가 N인 수열 A1, A2, ..., AN이 있다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i x: Ai를 x로 바꾼다. 2 l r: l ≤ i ≤ r에 속하는 모든 Ai중에서 짝수의 개수를 출력한다. 3 l r: l ≤ i ≤ r
www.acmicpc.net
세그먼트트리 문제다. 값을 갱신하는 함수에 재귀호출을 해주지 않아 "틀렸습니다"를 연달아 받는 실수를 해버렸다. 항상 그렇듯이 사소한 실수를 해버리면 허탈하다.
풀이
(Int, Int) 튜플의 형태로 트리를 생성한다. 0번째에는 짝수의 개수, 1번째에는 홀수의 개수를 담아내는 트리다. 입력된 수열을 기준으로 세그먼트 트리를 생성한다. 이후 쿼리에 맞춰서 동작을 수행하면 된다.
수열을 수정하는 쿼리의 경우, 새로 갱신될 값이 기존의 값과 홀짝 유무가 같다면, 수열의 값만 바꾸어 주고 트리는 갱신할 필요가 없다. 반대로 짝수 -> 홀수 혹은 그 반대의 경우가 입력된다면 갱신을 해주면 된다. 이때 루트 노드에서 리프 노드까지 범위 안의 값들을 입력된 조건에 맞게 (+1,-1) 혹은 (-1,+1) 연산을 수행하면 된다.
출력 쿼리의 경우 범위에 해당하는 노드의 값을 통째로 반환받은 뒤, 조건에 맞게 짝수, 홀수의 개수를 출력해 주었다.
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [12837] 가계부 (Hard) (0) | 2023.02.23 |
|---|---|
| [5676] 음주 코딩 (0) | 2023.02.23 |
| [14438] 수열과 쿼리 17 (0) | 2023.02.20 |
| [1306] 달려라 홍준 (0) | 2023.02.18 |
| [14428] 수열과 쿼리 16 (0) | 2023.02.17 |