수열과 쿼리37(백준 18436)

• init 함수를 이용해 tree를 형성합니다.
• change 함수를 이용해서 tree의 수정할 부분을 수정합니다.
• find 함수를 이용해서 구간에 해당하는 홀수 짝수 개수를 구합니다. 

import sys 
input =sys.stdin.readline
n= int(input())
originarr = [0]+ list(map(int, input().split()))
arr = [[0,0,0]]
for i in range(1, len(originarr)):
    odd,even = 0,0
    if 1 :
        if originarr[i]%2 == 1:
            odd += 1 
        else:
            even += 1 
    arr.append((originarr[i],even,odd))
tree = [[0,0,0]for _ in range((4*n)+1)]

def init(idx, s,e):
    if s== e :
        a,b,c = arr[s]
        tree[idx] = [a,b,c]
        return tree[idx]
    mid = (s+e)//2 
    l1,l2,l3 = init(idx*2, s,mid)
    r1,r2,r3 = init(idx*2+1, mid+1, e)
    
    tree[idx]  = [l1+r1, l2+r2, l3+r3] 
    return tree[idx] 
    
def change(idx,s,e,p,value) :
    if p< s or e<p :
        return 
    if s==e :
        a,b,c=arr[p]
        tree[idx] =[a,b,c]
        return 
    mid = (s+e)//2 
    change(idx*2,s,mid, p,value)    
    change(idx*2+1,mid+1,e, p,value)
    l1,l2,l3 =tree[idx*2]
    r1,r2,r3 =tree[idx*2+1]

    tree[idx]  = [l1+r1, l2+r2, l3+r3] 
    
def find(idx,l,r, s,e) :
    if r < s or e < l :
        return [0,0,0]
    if s<= l and r <= e :
        # a1,a2,a3 = tree[idx] 
        return tree[idx]
    mid = (l+r)//2 
    
    t1 = find(idx*2 , l, mid, s,e) 
    t2= find(idx*2+1 , mid+1, r, s,e) 
    return [t1[0]+t2[0],t1[1]+t2[1],t1[2]+t2[2] ]
    
        
    
init(1,1,n)
m= int(input())
for _ in range(m):
    a,b,c = map(int, input().split())
    if a == 1 :
        # b번자리 수를 c로 변경
        ev, od = 0,0
        if c%2 ==1:
            od+= 1 
        else :
            ev += 1 
        arr[b] = (c,ev,od) 
        change(1,1,n,b,c)
        # print(tree)
    elif a==2 :
        
        print(find(1,1, n, b,c)[1])
        
      #짝수 개수 구하기 b~ c 
    else : 
        # 홀수 개수 구하기 b~c 
        # r11,r12,r13 =find(1,1,n,b,c) 
        print(find(1,1,n,b,c)[2])