+⊕ and query

Let $K=31$. Every input value is smaller than $2^{30}$, so considering bits $0$ through $30$ is sufficient.

For $0 \leq j < K$ and $0 \leq r < 2^j$, put every index satisfying $A_i$ into a node . Bits are read from least significant to most significant. Thus, the two children of are and .

Index $i$ gives the following demand to node $(j,A_i \bmod 2^j)$:

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

Suppose a composition of additions and XORs maps an input value $z$ to $f(z)$. The lower $j$ bits of $f(z)$ depend only on the lower $j$ bits of . Therefore, all demands assigned to one node must be equal.

The following lemma is the key observation.

Lemma. Write $e_{j,r}$ for the change of bit $j$ at node $(j,r)$. These changes can be produced by a composition of additions and XORs if and only if, for every $1\le$, the following value is the same for every :

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

There is only one node at $j=0$, so no separate condition is needed there. The lemma can be proved by checking the identity for an addition and an XOR, then constructing a composition bit by bit from lower bits to higher bits. The additional bit $30$ prevents a wraparound that would only be valid modulo a power of two. The nonnegativity restriction can be met by using a sufficiently large common offset during the construction.

Call a node containing at least one index an active node. If one active node receives different demands, the transformation is impossible. Otherwise, denote its common demand by $d(j,r)$.

If both children of an active node $(j,r)$ are active, the value in the lemma is forced to be

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

If one child is empty, its value is free and creates no restriction. Consequently, a transformation exists if and only if both conditions below hold.

• All demands agree inside every active node.
• At each depth $j$, all nodes with two active children have the same value of $c(j,r)$.

Maintain a binary trie of the values in $A$, inserting bits from least significant to most significant. Each node stores the number of indices demanding $0$ and the number demanding $1$. We also maintain the total number of nodes with conflicting demands and, at every depth, the numbers of branching nodes forcing each of the two possible values of $c$.

When one element changes, remove the old pair $(A_i,B_i)$ from the trie and insert the new pair. Only one root-to-leaf path is affected. The status of a node can be updated using that node and its two children.

The time complexity of one query is $O(K)=O(\log 10^9)$, and the total space complexity is $O((N+Q)K)$.

Solution written by GPT5