XOR 병합

$P_0=0$, $P_i=A_1\oplus A_2\oplus\cdots\oplus A_i$라 하자. 전체 XOR을 $S=P_N$이라 하자.

병합 연산은 내부 원소 $P_i$ 하나를 삭제하는 것과 같다.

최종 수열의 모든 값이 $k$이고 길이가 $m$이라면 prefix XOR은

$$0,k,0,k,\cdots$$

꼴이다. 또한 전체 XOR $S$는 연산으로 변하지 않는다.

$S\ne 0$인 경우

$m$은 홀수이고 반드시 $k=S$이다. 따라서 목표 prefix XOR은 $0,S,0,S,\cdots,S$이다.

원래 $P$에서 값이 $0$ 또는 $S$인 원소만 남겨 보자. 이 수열을 같은 값이 연속한 구간들로 나눈 개수를 $C$라 하자. 각 구간에서 하나씩만 남기면 $0,S,0,S,\cdots,S$가 된다. 그 외의 prefix 원소는 모두 삭제해야 하므로 정답은

$$N+1-C$$

이다.

$S=0$인 경우

내부 prefix XOR $P_1,\cdots,P_{N-1}$ 중 $0$이 아닌 원소의 개수를 $$이라 하자. 에서 연속한 두 사이의 구간 수를 라 하자.

$k=0$을 선택하면 $0$이 아닌 내부 prefix XOR을 모두 삭제하면 되므로 비용은 $M$이다.

이제 $k\ne 0$을 고정하자. 모든 $0$ prefix를 남겨도 최적해가 나빠지지 않는다. 각 두 $0$ 사이에는 목표 수열에서 $k$가 정확히 하나 필요하다. 값 $k$가 이미 등장하는 구간 수를 라 하자. 그런 구간에서는 하나를 남겨 삭제 한 번을 아낄 수 있고, 등장하지 않는 구간에서는 하나를 삽입해야 한다. 따라서 비용은

$$M-H_k+(G-H_k)=M+G-2H_k$$

이다.

$H=\max H_k$라 하면 최종 정답은

$$\min(M,\ M+G-2H)$$

이다.

$H$는 왼쪽부터 prefix XOR을 훑으며 계산할 수 있다. $0$을 만날 때마다 구간 번호를 증가시킨다. $0$이 아닌 값 $v$에 대해서는 마지막으로 센 구간 번호와 등장 구간 수를 해시 테이블에 저장하면, 같은 구간에서 $v$가 여러 번 나와도 한 번만 셀 수 있다.

시간 복잡도는 기대값 기준 $O(N)$, 메모리 복잡도는 $O(N)$이다.

Solution written by GPT5.6

TMI. 참고로 원래는 분할 연산이 있었습니다.

• 분할: $1\le i<\lvert A\rvert, x\oplus y=A_i$를 만족하는 정수 $i,x,$를 골라 의 번째 원소를 삭제하고 그 위치에 를 삽입한다.

이는 위의 prefix XOR 접근으로 보았을 때 내부 원소를 추가하는 것과 같고, 이는 삭제보다 효율적이지 않아 답에는 영향을 주지 않습니다.