18436 수열과 쿼리 37 python

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

18436번: 수열과 쿼리 37

 

 

 

문제 접근

세그먼트 트리문제

짝수와 홀수를 따로 저장해야할까 고민했는데, 저장할때 2로 나눠서 저장하면 한번에 계산된다는것을 파악했다.

0아니면 1로 저장을 한 다음 구간 합을 구한다.

구하려는 범위의 구간합은 홀수고 범위에서 구간합을 빼면 짝수가 나온다

 

 

 

코드

import sys
import math

input = sys.stdin.readline
"""
2243
%2했을 때
1의 개수가 홀수의 개수 
end-start+1에서 1개수 뺀게 짝수의 개수

"""

def init(start, end, index):
  if start != end:
    mid = (start + end) // 2
    tree[index] = init(start, mid, index*2) + init(mid+1, end, index*2+1)
  return tree[index]

def ans(targetStart, targetEnd, start, end, index):
  if targetStart>end or targetEnd<start:
    return 0
  if targetStart<=start and end<=targetEnd:
    return tree[index]
  mid = (start+end) // 2
  return ans(b, c, start, mid, index*2) + ans(b, c, mid+1, end, index*2+1)


def update(target, val):
  index = target + node - 1
  tree[index] = val%2
  while index>1:
    index//=2
    tree[index] = tree[index*2] + tree[index*2+1]
    

N = int(input())
node = 2**math.ceil(math.log2(N))
tree = [0] * (node*2+1)
tree[node:node+N] = list(map(int,input().split()))
for i in range(N):
  tree[node+i] %= 2
M = int(input())

init(1, node, 1)
for m in range(M):
  a,b,c = map(int,input().split())
  if a == 1:
    update(b, c)
  elif a == 2:
    print(c-b+1 - ans(b, c, 1, node, 1))
  else:
    print(ans(b, c, 1, node, 1))