[BOJ] 13704 수열과 쿼리 11

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

13704번: 수열과 쿼리 11

알고리즘: Mo's

 

시간복잡도: $O((N+M)\sqrt N)$

 

---

XOR 연산을 하는 문제다.

아래 두가지 관찰만 하면 쉽게 접근이 가능하다.

 

1. a ^ a = 0 : 자기 자신을 xor하면 0이 나옴

2. a ^ 0 = a : xor 0을 하면 자기 자신이 나옴

 

따라서 $a[i]=A_1$^$A_2$^...^$A_i$ 로 두면,

$a[j]$^$a[i-1]=A_i$^$A_{i+1}$^...^$A_j$ 이다.

 

$a[j]$^$a[i-1]=K$를 정리하면,

$a[j]=K$^$a[i-1]$ 가 되므로

Mo's 로 접근하여 $a[j]$를 추가 및 제거를 할 때, $K$^$a[i-1]$의 개수를 더하거나 빼주면 된다.

 

 

query [l, r]의 구간을 [l-1, r]로 저장해주면 구현이 깔끔해진다.