Generic Queries

• 누적 합을 XOR에 적용한 문제
• 그냥 구간 합 구하기 4의 XOR 버전이라고 보면 된다. 코드도 거의 동일하다.
• 누적 XOR을 O(n)에 만들면, m개의 쿼리를 각각 O(1)에 해결 가능. 총 시간복잡도는 O(n+m)

"""Solution code for "BOJ 16713. Generic Queries".

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

import sys


def main():
    N, Q = [int(x) for x in sys.stdin.readline().split()]
    v = 0
    prefix_xor = [v] + [v := v ^ int(x) for x in sys.stdin.readline().split()]
    answer = 0
    for _ in range(Q):
        s, e = [int(x) for x in sys.stdin.readline().split()]
        answer ^= prefix_xor[e] ^ prefix_xor[s - 1]
    print(answer)


if __name__ == '__main__':
    main()