+⊕과 쿼리

$K=31$로 둔다. 모든 입력 값은 $2^{30}$보다 작으므로, $0$번 비트부터 $30$번 비트까지 고려하면 충분하다.

$0 \leq j < K$와 $0 \leq r < 2^j$에 대해, $A_i<mrow></mrow>$인 모든 를 하나의 노드 에 넣는다. 비트는 낮은 자리부터 읽는다. 따라서 의 두 자식은 과 이다.

각 인덱스 $i$는 노드 $(j,A_i \bmod 2^j)$에 다음 요구값을 준다.

$$d_{i,j}=\operatorname{bit}_j(A_i\mathbin{\mathrm{xor}}B_i).$$

덧셈과 XOR을 합성하여 얻은 함수가 입력값 $z$를 출력값 $f(z)$로 보낸다고 하자. $f(z)$의 하위 $j$개 비트는 $z$의 하위 $$개 비트만으로 결정된다. 그러므로 같은 노드에 속한 모든 인덱스의 요구값은 같아야 한다.

다음 보조정리가 핵심이다.

보조정리. 각 노드 $(j,r)$에 $j$번 비트의 변화량 $e_{j,r}$를 적었다고 하자. 이 변화량들이 덧셈과 XOR의 합성으로 만들어질 필요충분조건은, 각 $1\le j\le K-$에 대해 다음 값이 모든 에서 같다는 것이다.

$$e_{j,r}\mathbin{\mathrm{xor}}e_{j+1,r}\mathbin{\mathrm{xor}}e_{j+1,r+2^j}$$

$j=0$에는 노드가 하나뿐이므로 별도 조건이 없다. 이 보조정리는 덧셈과 XOR 각각에 대해 식을 확인하고, 비트별로 아래에서 위로 합성을 구성하여 증명할 수 있다. $30$번 비트를 추가로 고려했으므로 모듈러 연산에서 생길 수 있는 넘침도 허용되지 않는다. 음이 아닌 조건은 구성 과정에서 충분히 큰 공통 이동량을 사용하면 만족시킬 수 있다.

현재 인덱스가 하나 이상 들어 있는 노드를 extbf{활성 노드}라고 하자. 같은 노드의 요구값이 서로 다르면 바로 불가능하다. 그렇지 않으면 그 공통 요구값을 $d(j,r)$로 둔다.

활성 노드 $(j,r)$의 두 자식이 모두 활성이라면 보조정리의 값은 다음과 같이 강제로 정해진다.

$$c(j,r)=d(j,r)\mathbin{\mathrm{xor}}d(j+1,r)\mathbin{\mathrm{xor}}d(j+1,r+2^j).$$

자식 하나가 비어 있다면 그 자식의 값을 자유롭게 정할 수 있으므로 조건이 생기지 않는다. 따라서 변환이 가능한 필요충분조건은 다음 두 가지이다.

• 모든 활성 노드에서 요구값이 하나로 일치한다.
• 각 깊이 $j$마다, 두 자식이 모두 활성인 모든 노드의 $c(j,r)$가 하나로 일치한다.

수열 $A$의 값을 낮은 비트부터 넣은 이진 트라이를 관리한다. 각 노드에는 요구값이 $0$인 인덱스 수와 $1$인 인덱스 수를 저장한다. 또한 요구값이 충돌하는 노드의 총개수와, 각 깊이에서 강제된 $c$가 $0$인 노드 수와 $1$인 노드 수를 저장한다.

하나의 원소가 바뀌면 이전 $(A_i,B_i)$를 트라이에서 지우고 새로운 $(A_i,B_i)$를 넣는다. 영향을 받는 노드는 하나의 루트-리프 경로뿐이다. 각 노드와 그 두 자식만 보면 해당 노드의 상태를 갱신할 수 있다.

한 쿼리의 시간 복잡도는 $O(K)=O(\log 10^9)$이고, 전체 공간 복잡도는 $O((N+Q)K)$이다.

Solution written by GPT5