Weird Decimal XOR

Number the colors Red, Orange, Yellow, Blue, Purple as $0,1,2,3,4$, and represent the state by $0$ or $1$. Use the following mapping $f$:

$$(f(0),f(1),\cdots,f(9))=(0,5,6,1,2,7,8,3,4,9).$$

For a digit $d$, $f(d)$ is the unique integer from $0$ to $9$ satisfying both conditions below.

• $f(d)\bmod 5$ is the color index of $d$.
• $f(d)\bmod 2$ is the state of $d$.

Color composition is addition of color indices modulo $5$, while XOR of two states is addition modulo $2$. Therefore, by the Chinese remainder theorem,

$$f(x\diamond y)\equiv f(x)+f(y)\pmod{10}.$$

Let $d_j(A_i)$ be the digit at the $10^j$ position of $A_i$. Define a prefix sum for every decimal position by

$$S_i^j=\sum_{k=1}^{i} f(d_j(A_k))\pmod{10},\qquad S_0^j=0.$$

The result at decimal position $j$ for a subarray $[l,r]$ is $0$ if and only if $S_{l-1}^j=S_r^j$.

The whole weird decimal XOR is $0$ exactly when this condition holds at every decimal position. Since $0\le A_i\le10^{18}$, only the $19$ positions $j=0,1,\cdots,18$ matter. Define

$$S_i=(S_i^0,S_i^1,\cdots,S_i^{18}).$$

Then the weird decimal XOR of $A_l,A_{l+1},\cdots,A_r$ is $0$ if and only if $S_{l-1}=S_r$.

Subtask 1

If $A_i\le9$, only the ones digit can be nonzero, so each $S_i$ is effectively a single residue modulo $10$. Store prefix occurrence counts for each residue $0,1,\cdots,9$. In a query $[L,R]$, obtain the frequency of every residue among prefix positions $L-1,L,\cdots,R$. If a residue appears $c$ times, it contributes $\binom{c}{2}$ equal-position pairs. Thus one query takes $O(10)$ time.

The time complexity is $O(N+10Q)$ and the space complexity is $O(10N)$.

Full constraints

Now $S_i$ is a vector of length $19$, so the entire state space is far too large to enumerate. However, only $S_0,S_1,\cdots,S_N$ can actually occur. Sort these vectors lexicographically and assign the same integer ID to equal vectors.

Each query $[L,R]$ is now the problem of counting pairs of distinct positions with equal IDs inside the prefix-position interval $[L-1,R]$.

Process these queries offline with Mo's algorithm. If the current interval contains $c$ occurrences of ID $v$, adding one more $v$ increases the answer by $c$. When removing $v$, first decrease its frequency by one and then subtract the remaining frequency from the answer.

Building the vectors costs $O(19N)$, coordinate compression costs $O(19N\log N)$, and Mo's algorithm costs $O((N+Q)\sqrt N)$. Therefore the total time complexity is

$$O(19N\log N+(N+Q)\sqrt N),$$

and the space complexity is $O(19N+Q)$.

Solution written by GPT5.6