이진수열과 쿼리

편의상 인덱스를 $0$부터 $N-1$까지 사용한다. 모든 인덱스는 $N$으로 나눈 나머지로 해석한다.

같은 시작점에서 연산을 두 번 하면 서로 상쇄된다. 따라서 시작점 $i$에서 연산을 홀수 번 하는지를 $x_i\in\{0,1\}$로 두면 충분하다.

위치 $i$가 최종적으로 0이 되려면

$$a_i=\bigoplus_{j=i-K+1}^{i}x_j$$

가 성립해야 한다. 인접한 두 식을 XOR하면

$$x_i\oplus x_{i-K}=\Delta_i,\qquad \Delta_i=a_i\oplus a_{i-1}$$

를 얻는다.

$d=\gcd(N,K)$, $m=N/d$, $h=K/d$라 하자. 는 정확히 개의 길이 인 순환으로 분해된다.

나머지 클래스 $r$에 대해

$$P_r=\bigoplus_{i\equiv r\pmod d}a_i$$

라 하자. 한 순환에서 모든 차분식을 XOR한 값은 $P_r\oplus P_{r-1}$이다. 따라서 차분식이 모순 없이 풀리기 위한 필요충분조건은

$$P_0=P_1=\cdots=P_{d-1}$$

이다.

각 순환을

$$v_t=r+tK\pmod N,\qquad t=0,\ldots,m-1$$

순서로 놓는다. 한 canonical 해를

$$x_{v_0}=0,\qquad x_{v_t}=x_{v_{t-1}}\oplus\Delta_{v_t}\quad(t\ge1)$$

로 잡는다. 순환 $r$에서 $x$가 $1$인 개수를 $c_r$라 하자.

차분식만 보면 각 순환 전체를 뒤집는 자유변수 $y_r$가 하나씩 있다. $y_r=0$의 비용은 $c_r$, 의 비용은 이다. 따라서 차분식만 만족시키는 최소 비용은

$$B=\sum_r\min(c_r,m-c_r)$$

이다.

차분식은 원래 식들의 차이만 사용했으므로 원래 식 하나를 더 맞춰야 한다. 위치 $0$의 식에 대한 잔여값을

$$E=a_0\oplus\bigoplus_{j=-K+1}^{0}x_j$$

라 하자. 목표는 $E=0$이다.

길이 $K$인 구간에는 각 나머지 클래스의 원소가 정확히 $h=K/d$개씩 들어간다.

$h$가 짝수이면 한 순환 전체를 뒤집어도 $E$가 변하지 않는다. 따라서 $E=1$이면 불가능하고, $E=0$이면 답은 $B$이다.

$h$가 홀수이면 각 $y_r$가 $E$를 한 번씩 뒤집는다. 즉

$$y_0\oplus y_1\oplus\cdots\oplus y_{d-1}=E$$

를 만족해야 한다. 비용만 보고 선호하는 선택을

$$z_r=[c_r>m/2],\qquad Z=\bigoplus_r z_r$$

라 하자. $Z=E$이면 답은 $B$이다. 그렇지 않으면 순환 하나의 선택을 반대로 해야 하며 추가 비용은

$$\min_r|m-2c_r|$$

이다.

이제 쿼리를 처리한다. $a_p$를 뒤집으면 $\Delta_p$와 $\Delta_{p+1}$만 뒤집히고, 만 뒤집힌다. 따라서 모든 가 같은지는 인 클래스의 개수만 관리하면 에 판별할 수 있다.

순환 안에서 $\Delta_{v_s}$가 뒤집히면 $s\ge1$일 때 canonical 해의

$$x_{v_s},x_{v_{s+1}},\ldots,x_{v_{m-1}}$$

가 모두 뒤집힌다. $s=0$인 $\Delta_{v_0}$는 순환의 닫힘 조건에만 쓰이므로 canonical 해 자체는 바뀌지 않는다.

모든 순환을 순환 순서대로 이어 붙인 길이 $N$ 배열을 만들고, 구간 뒤집기와 구간의 $1$ 개수 질의를 지원하는 lazy segment tree를 사용한다. 각 쿼리는 suffix 뒤집기 최대 두 번과 영향을 받은 순환의 $c_r$ 재계산만 필요하다.

각 순환의 $c_r$가 바뀔 때 다음 값을 함께 갱신한다.

• $B=\sum_r\min(c_r,m-c_r)$

$E$도 매번 직접 다시 계산할 필요가 없다. 각 $\Delta_u$를 뒤집을 때 canonical 해에서 뒤집히는 suffix가 $E$의 길이 $K$ 구간과 몇 개 겹치는지의 홀짝을 $impact[u]$로 전처리한다. 순환의 시작점에서는 이다. 쿼리 에 대해

$$E\mathrel{\oplus}=[p=0]\oplus impact[p]\oplus impact[p+1]$$

로 갱신할 수 있다.

따라서 각 쿼리의 답은 다음과 같다.

• $P_r$들이 모두 같지 않으면 -1.
• $h$가 짝수이면 $E=1$일 때 -1, 아니면 $B$.
• $$가 홀수이면 .

각 테스트 케이스의 전처리는 $O(N\log N)$, 각 쿼리는 $O(\log N)$이다. 전체 시간복잡도는 $O((N+Q)\log N)$이고 메모리는 이다.

Solution written by GPT5.6