로 둔다. 모든 입력 값은 보다 작으므로, 번 비트부터 번 비트까지 고려하면 충분하다.
와 에 대해, 인 모든 를 하나의 노드 에 넣는다. 비트는 낮은 자리부터 읽는다. 따라서 의 두 자식은 과 이다.
각 인덱스 는 노드 에 다음 요구값을 준다.
덧셈과 XOR을 합성하여 얻은 함수가 입력값 를 출력값 로 보낸다고 하자. 의 하위 개 비트는 의 하위 개 비트만으로 결정된다. 그러므로 같은 노드에 속한 모든 인덱스의 요구값은 같아야 한다.
다음 보조정리가 핵심이다.
보조정리. 각 노드 에 번 비트의 변화량 를 적었다고 하자. 이 변화량들이 덧셈과 XOR의 합성으로 만들어질 필요충분조건은, 각 에 대해 다음 값이 모든 에서 같다는 것이다.
에는 노드가 하나뿐이므로 별도 조건이 없다. 이 보조정리는 덧셈과 XOR 각각에 대해 식을 확인하고, 비트별로 아래에서 위로 합성을 구성하여 증명할 수 있다. 번 비트를 추가로 고려했으므로 모듈러 연산에서 생길 수 있는 넘침도 허용되지 않는다. 음이 아닌 조건은 구성 과정에서 충분히 큰 공통 이동량을 사용하면 만족시킬 수 있다.
현재 인덱스가 하나 이상 들어 있는 노드를 extbf{활성 노드}라고 하자. 같은 노드의 요구값이 서로 다르면 바로 불가능하다. 그렇지 않으면 그 공통 요구값을 로 둔다.
활성 노드 의 두 자식이 모두 활성이라면 보조정리의 값은 다음과 같이 강제로 정해진다.
자식 하나가 비어 있다면 그 자식의 값을 자유롭게 정할 수 있으므로 조건이 생기지 않는다. 따라서 변환이 가능한 필요충분조건은 다음 두 가지이다.
수열 의 값을 낮은 비트부터 넣은 이진 트라이를 관리한다. 각 노드에는 요구값이 인 인덱스 수와 인 인덱스 수를 저장한다. 또한 요구값이 충돌하는 노드의 총개수와, 각 깊이에서 강제된 가 인 노드 수와 인 노드 수를 저장한다.
하나의 원소가 바뀌면 이전 를 트라이에서 지우고 새로운 를 넣는다. 영향을 받는 노드는 하나의 루트-리프 경로뿐이다. 각 노드와 그 두 자식만 보면 해당 노드의 상태를 갱신할 수 있다.
한 쿼리의 시간 복잡도는 이고, 전체 공간 복잡도는 이다.
Solution written by GPT5
