수열과 쿼리 37

• A 수열에 대응되는 B 수열이 있어서, A[i]가 홀수이면 B[i]=1, 짝수이면 B[i]=0 이라고 하자.
• A[l:r]중에서 홀수의 갯수를 구하는 것은 sum(B[l:r])과 같고, 짝수의 갯수는 (r-l+1)-sum(B[l:r]) 과 같다.
• 결국 포인트 업데이트가 있는 구간 합 문제이므로, 펜윅트리를 사용해서 각 쿼리를 O(logn)에 처리할 수 있다.
• 펜윅트리 구축에 O(n), m개의 쿼리를 각 O(logn)에 처리하는 데에 O(mlogn). 도합 O(n+mlogn)에 해결 가능하다

"""Solution code for "BOJ 18436. 수열과 쿼리 37".

- Problem link: https://www.acmicpc.net/problem/18436
- Solution link: http://www.teferi.net/ps/problems/boj/18436
"""

import sys
from teflib import fenwicktree


def main():
    N = int(sys.stdin.readline())  # pylint: disable=unused-variable
    A = [int(x) for x in sys.stdin.readline().split()]
    M = int(sys.stdin.readline())
    fenwick = fenwicktree.FenwickTree(x % 2 for x in A)
    for _ in range(M):
        query = [int(x) for x in sys.stdin.readline().split()]
        if query[0] == 1:
            _, i, x = query
            fenwick.set(i - 1, x % 2)
        elif query[0] == 2:
            _, l, r = query
            print(r - l + 1 - fenwick.query(l - 1, r))
        else:
            _, l, r = query
            print(fenwick.query(l - 1, r))


if __name__ == '__main__':
    main()

• Dependency: teflib.fenwicktree.FenwickTree