[백준 18436번] 수열과 쿼리 37 (Python3)

import sys
input = sys.stdin.readline

def makeseg(start,end,x):
  if start == end:
    seg[x] = data[start]
  else:
    mid = (start+end)//2
    seg[x] = makeseg(start,mid,x*2)+makeseg(mid+1,end,x*2+1)
  return seg[x]

def updateseg(diff,n,start,end,x):
  seg[x] += diff
  if start == end:
    return
  mid = (start+end)//2
  if n <= mid:
    updateseg(diff,n,start,mid,x*2)
  else:
    updateseg(diff,n,mid+1,end,x*2+1)

def printseg(a,b,start,end,x):
  if a==start and b==end:
    return seg[x]
  mid = (start+end)//2
  if b<=mid:
    return printseg(a,b,start,mid,x*2)
  if a>mid:
    return printseg(a,b,mid+1,end,x*2+1)
  return printseg(a,mid,start,mid,x*2)+printseg(mid+1,b,mid+1,end,x*2+1)

N = int(input())
data = [*map(lambda x:x%2,map(int,input().split()))]
seg = {}
makeseg(0,N-1,1)

M = int(input())
for i in range(M):
  q,a,b = map(int,input().split())
  if q == 1:
    a,b = a-1,b%2
    diff = b-data[i]
    data[a] = b
    updateseg(diff,a,0,N-1,1)
  elif q == 3:
    print(printseg(a-1,b-1,0,N-1,1))
  else:
    print(b-a+1-printseg(a-1,b-1,0,N-1,1))

전형적인 세그먼트 트리 문제.

 

값이 x일때 데이터값을 x%2 저장하고, 합에 대한 세그먼트 트리를 만들면 된다.

그러면 홀수의 개수는 세그먼트 트리의 값이고, 짝수의 개수는 (범위의 크기+1-세그먼트트리값) 이 된다.

 

오늘의 교훈) 세그먼트 트리 짤때 실수하지 말자