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-세그먼트트리값) 이 된다.
오늘의 교훈) 세그먼트 트리 짤때 실수하지 말자