https://physicsmathcoumputer.tistory.com/82
이런 식의 구간 쿼리의 문제들은 차이를 살펴보면 풀린다.
arr[x]를 x-1번째 호떡과 x번째 호떡이 다르다면 1, 같다면 0으로 두자. 즉 arr[x]=v[x]^v[x-1]
2번 쿼리는 다음과 같이 해석된다.
- 1.arr[x]=0인 (x>=2)를 고른다.
- 만약 arr[1]+arr[2]+...+arr[x]가 2로 나누어 떨어진다면 arr[1]과 arr[x]에 1을 xor한다.
- 만약 arr[1]+arr[2]+...+arr[x]가 2로 나누어 떨어지지 않는다면 arr[x]에 1을 xor한다.
이걸 이용해 새로운 문제로 치환하면 쉽게(?) 풀린다. 힌트는 arr[1]을 고를 수 없다는게 포인트이다. (즉 arr[1]을 어떻게 목표에 맞출까..)