====== XOR ======

===== 풀이 =====
  * 구간 업데이트 + 구간 쿼리 문제의 [[ps:구간 쿼리#구간 xor 쿼리]] 버전 문제
    * [[ps:problems:boj:12844|XOR]]과 제목이 똑같지만, 다른 문제이다. 그쪽은 구간 업데이트/포인트 쿼리.
  * [[ps:세그먼트 트리#lazy propagation]]를 이용하면 쉽게 구현이 가능하다
    * [[ps:세그먼트 트리#lazy propagation]]에서 사용한 노테이션대로, f,g,h 를 정의하면
      * f(x, y) = x^y.
      * g(x, c, size) = x^c if size % 2 == 1 else x
      * h(c1, c2) = c1^c2
    * 구간에 대해서 xor을 적용하게 될때만 신경쓰면 된다. f(a1^c,a2^c,...,an^c) = (a1^c)^(a2^c)^...(an^c) = (a1^a2^...^an)^(c^c^...^c) 가 되고, 리프노드가 아닌 한 구간 내의 원소 갯수는 모두 2^k로 짝수이므로, 결과는 그대로 (a1^a2^...^an)이 되어 변하지 않는다.
    * 세그먼트 트리를 구축하는 데에 O(n), m개의 쿼리를 각각 O(logn)에 처리하는 데에 O(mlogn), 합쳐서 O(n+mlogn)이다
  * 하지만, n과 m이 500,000으로 꽤 크다보니 이렇게는 python으로는 시간 내에 통과가 어렵다 (pypy로 3000ms 대에 통과되었었다).
  * 대신, [[ps:구간 쿼리#구간 xor 쿼리]]에서 설명했듯이, 두개의 펜윅트리를 이용해서 처리하는 방법을 사용할 수가 있다. 이렇게 할 경우에도 시간 복잡도 자체는 동일하다. 펜윅트리를 구축하는 데에 O(n), m개의 쿼리를 각각 O(logn)에 처리하는 데에 O(mlogn), 합쳐서 O(n+mlogn)이 된다. 하지만, 상수값이 줄어들기 때문에, python으로도 5536ms에 통과된다 (Pypy로는 1252ms)

===== 코드 =====

==== 코드 1 - 두개의 펜윅트리 ====
<dkpr py>
"""Solution code for "BOJ 12844. XOR".

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

import sys
from teflib import fenwicktree


def main():
    N = int(sys.stdin.readline())
    A = [int(x) for x in sys.stdin.readline().split()]    
    fenwick1 = fenwicktree.XorFenwickTree(N + 1)
    fenwick2 = fenwicktree.XorFenwickTree(A + [0])
    M = int(sys.stdin.readline())
    for _ in range(M):
        query = [int(x) for x in sys.stdin.readline().split()]
        if query[0] == 1:
            _, i, j, k = query
            fenwick1.update(i, k)
            fenwick1.update(j + 1, k)
            if not i % 2:
                fenwick2.update(i, k)
            if j % 2:
                fenwick2.update(j + 1, k)
        else:
            _, i, j = query
            res = fenwick2.query(0, j + 1) ^ fenwick2.query(0, i)
            if not i % 2:
                res ^= fenwick1.query(0, i)
            if j % 2:
                res ^= fenwick1.query(0, j + 1)
            print(res)


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:fenwicktree#XorFenwickTree|teflib.fenwicktree.XorFenwickTree]]

==== 코드 2 - 세그먼트 트리 + 레이지 프로파게이션 ====
<dkpr py>
"""Solution code for "BOJ 12844. XOR".

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

import operator
import sys
from teflib import segmenttree


def main():
    N = int(sys.stdin.readline())  # pylint: disable=unused-variable
    A = [int(x) for x in sys.stdin.readline().split()]
    lazy_segtree = segmenttree.LazySegmentTree(
        A,
        merge=operator.xor,
        update_value=lambda v, p, size: (v ^ p) if size % 2 else v,
        update_param=operator.xor,
        should_keep_update_order=False)
    M = int(sys.stdin.readline())
    for _ in range(M):
        query = [int(x) for x in sys.stdin.readline().split()]
        if query[0] == 1:
            _, i, j, k = query
            lazy_segtree.range_update(i, j + 1, k)
        else:
            _, i, j = query
            print(lazy_segtree.query(i, j + 1))


if __name__ == '__main__':
    main()
</dkpr>
  * Dependency: [[:ps:teflib:segmenttree#LazySegmentTree|teflib.segmenttree.LazySegmentTree]]

{{tag>BOJ ps:problems:boj:플래티넘_3}}