Editorial

---

D

summary:

배열 $a$가 주어지는데, 구간 $(l,r)$을 정해서 $x$와 $a_l,a_{l+1},\dots,a_r$을 $\oplus$시킬 수 있다. 이때 비용은 $\lceil \frac{r-l+1}{2} \rceil$이다.

최소의 비용으로 모든 수를 0으로 만드는 비용을 구하는 문제이다.

solution:

구간의 길이가 1,2인 것만 연산에서 사용한다.

만약 어떤 구간 $(l,r)$의 $a_l \oplus a_{l+1} \oplus \dots \oplus a_r$가 0이면 $r-l$(구간의 길이-1)번 하면 그 구간은 전부 0이 된다.

비용을 최소화하려면 그러한 구간(0이 되는 구간, 겹치지 않는)이 가장 많게 해야 할 것이다.

ans를 n으로 일단 가정하고,

set에 0~i까지의 누적 xor값을 저장해두면서, 만약 겹치는 것이 등장하면 (= 어떤 $j+1$에서 $i$까지 xor값이 0이라는 뜻) ans에 -1을 하고 set을 비워준다.

그러면 겹치는 개수만큼 - 되므로 (xor해서 0이 되는 구간 등장시마다 비용이 구간길이 -1 이 되므로)

답을 구할 수 있다.

opinion:

문제가 어렵지 않다. 왜 생각을 해내지 못했을까? 문제들마다 획기적인 방법이 존재한다고 생각하고 그런 것을 찾으려고 해서일까?