[ BOJ] 18436 수열과 쿼리 37

 

 

https://www.acmicpc.net/problem/18436

18436번: 수열과 쿼리 37

알고리즘: Segment tree

 

시간복잡도: $O((N+M)logN)$

---

접근:

1. 구간 쿼리 및 쿼리 개수 $(M\le 10^5)$

 

정해진 구간 내의 짝수 및 홀수의 개수를 구하는 문제이다.

 

$A_i$가 홀수이면 1, 짝수이면 0으로 segment tree의 리프 노드에 저장해두고,

부모 노드는 자식 노드들의 합으로 표현해주면 구간 내 홀수의 개수를 구해줄 수 있다.

(짝수의 개수는 (r-l+1)-홀수 개수로 구해줄 수 있다.)

 

만약 $A_i$의 값이 홀수에서 짝수로 변경되었다면,

해당 리프 노드부터 root까지 탐색하면서 값을 1씩 빼주면서 트리를 갱신할 수 있다.