gstar1106   3년 전

다른 질문에 있는 반례는 모두 실행시켜 보았습니다.

slah007   3년 전

우선 위 코드의 문제는, 102번 줄에서 segment tree에 하는 업데이트 말고도 101번 (빈)줄에서 arr[index] 역시 업데이트해야 합니다. 만약 같은 arr[index]가 홀->짝->홀로 업데이트되는 경우 이 코드상에서는 홀->짝만 업데이트하고 그 후 짝->홀로는 업데이트가 안됩니다.
input:
6
1 2 3 4 5 6
3
1 2 3
1 2 2
2 1 6

output:
2 (3이 나와야 함)    https://ideone.com/NzMTfr


또한, 이 문제는 segment tree까지 쓰지 않아도 평방분할(sqrt decomposition)을 쓰면 매우 쉽게 풀립니다.

1. 전체 구간 [1,N]을 m=sqrt(N)개의 소구간 [1,m], [m+1, 2m], ... [m*(m-1)+1, m^2]으로 나눈다.

2. 각 소구간에서 홀수, 짝수의 개수를 구해 저장한다. 여기까지 O(N).

3. 만약 쿼리[l, r]가 들어오면, 이는 [l,A*m] + (A~B까지 소구간 B-A개) + [B*m+1, r]로 나눌 수 있습니다. 양쪽 끝 [l, A*m]과 [B*m+1]은 각각이 소구간보다 짧으므로 길이가 최대 2*m이고, 중간에 있는 구간의 수도 최대 m이므로 총 O(m)만에 처리 가능.

4. 업데이트가 들어오면 해당 소구간에서 값만 변경하면 됩니다. O(1)

모든 쿼리에 대해 처리하면 총 O(N+Q*sqrtN)

댓글을 작성하려면 로그인해야 합니다.