수열과 어렵지 않은 쿼리

• a[i] 와 a[i+1]이 달라지는 변경점들의 위치들을 기록해놓으면, 일치 구간의 갯수는 {변경점의 개수} + 1 로 구할수 있다
• 어떤 구간내의 변경점의 개수를 계산하는 것은, 변경점이면 1, 아니면 0을 저장해 놓게 되면 단순한 구간합 쿼리로 처리할 수 있다. 펜윅트리나 세그먼트 트리를 이용하면 O(logn)에 처리가능
• a[i]의 값을 바꾸게 되면, 변경점의 값이 바뀔수 있는 곳은 a[i-1]과 a[i], a[i]과 a[i+1] 이렇게 두 곳 뿐이다. 이렇게 두 곳을 point update 해주면 되므로, 이것 역시 펜윅트리나 세그트리에서 O(logn)에 처리 가능
• 총 시간 복잡도는 O(n+qlogn)

"""Solution code for "BOJ 31222. 수열과 어렵지 않은 쿼리".

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

Tags: [fenwick tree]
"""


import itertools
import sys
from teflib import fenwicktree


def main():
    n, q = [int(x) for x in sys.stdin.readline().split()]
    A = sys.stdin.readline().split()

    diff = [0] + [0 if x == y else 1 for x, y in itertools.pairwise(A)]
    fenwick = fenwicktree.FenwickTree(diff)

    for _ in range(q):
        match sys.stdin.readline().split():
            case '1', i, x:
                i = int(i) - 1
                A[i] = x
                if i > 0:
                    fenwick.set(i, 1 if A[i] != A[i - 1] else 0)
                if i < n - 1:
                    fenwick.set(i + 1, 1 if A[i] != A[i + 1] else 0)
            case '2', l, r:
                l, r = int(l) - 1, int(r) - 1
                print(fenwick.query(l + 1, r + 1) + 1)


if __name__ == '__main__':
    main()

• Dependency: teflib.fenwicktree.FenwickTree