MEXOR

$P(l,r)$를 $A_l,\ldots,A_r$에 있는 $0$의 개수를 $2$로 나눈 나머지라고 하자. 모든 원소를 한 개씩 나누어 얻는 XOR 값은 $P(1,N)$이다.

분할에서 길이가 긴 구간 $[l,r]$을 하나 선택하고 그 밖의 원소를 한 개씩 나누면, 기본 XOR 값에서 바뀌는 양은 $\mathrm{MEX}(l,r)\oplus P(l,r)$이다. 따라서 여러 개의 서로 겹치지 않는 구간을 골라, 이 변화량을 XOR하는 문제로 바꿀 수 있다.

$\mathrm{MEX}(l,r)=0$이면 변화량은 $0$이다. $\mathrm{MEX}(l,r)=1$일 때는 구간에 이 없으며, 의 개수가 홀수이면 변화량이 이다. 짝수 개의 이 있는 구간은 내부의 연속한 두 의 위치 사이에 이 없는 작은 구간으로 대체할 수 있다. 이 작은 구간의 변화량은 이다.

$\mathrm{MEX}(l,r)=m\ge2$인 구간은, $0,1,\ldots,m-1$을 전부 포함하는 최소 길이의 부분구간 을 내부에서 선택할 수 있다. 이 부분구간의 양 끝 원소는 각각 한 번만 등장하며 보다 작다. 이러한 을 모든 시작점과 끝점에 대해 MEX와 등장 횟수를 갱신하면서 열거한다.

원래 구간과 핵심 구간 사이에서 제거된 $0$의 개수가 짝수라면 핵심 구간만 써도 변화량이 같다. 홀수라면 핵심 구간의 왼쪽 또는 오른쪽에서 가장 가까운 $0$까지 확장하면 된다. 이 확장이 원래 구간 안에 있는 경우 MEX는 바뀌지 않는다. 따라서 모든 핵심 구간과, MEX가 그대로인 가장 가까운 $0$까지의 왼쪽 또는 오른쪽 확장 구간을 후보로 추가한다. 핵심 구간은 총 $O(N)$개이므로 후보도 $O(N)$개이다.

$dp[i]$를 $[1,i]$ 안에서 서로 겹치지 않는 후보 구간을 선택해 얻을 수 있는 변화량 XOR 값들의 집합이라고 하자. 후보를 선택하지 않고 $i$를 넘기는 전이와, $i$에서 끝나는 후보 $[l,i]$를 선택하여 의 모든 원소에 해당 구간의 변화량을 XOR하는 전이를 적용한다.

모든 구간의 MEX는 전체 수열의 MEX 이하이다. 이를 $G$라고 하면 가능한 XOR 값은 $2^{\lceil\log_2(G+1)\rceil}$보다 작다. 비트 집합으로 DP를 구현하면 전체 시간 복잡도는 $O(N^2)$, 공간 복잡도는 이다. 답은 의 각 원소에 을 XOR한 값 중 최댓값이다.