For \(0 \leq k\), let us define \(w_k=0 \oplus 1 \oplus \cdots \oplus (k-1)\).

We want to count \((i,j)\) such that \(L \leq i < j \leq R+1\) and \(w_i \oplus w_j=V\).

After a small transformation, it comes down to a subroutine of counting \((i,j)\) such that \(0 \leq i < A, 0 \leq j < B, w_i \oplus w_j=V\).

The values of \(w_k\) are simple when classified modulo \(4\). Specifically, we have:

• \(w_{4x}=0\)
• \(w_{4x+1}=4x\)
• \(w_{4x+2}=1\)
• \(w_{4x+3}=4x+3\)

Thus, we just need to fix the remainders of \(i\) and \(j\) divided by \(4\) and solve all \(16\) cases. In reality, the cases \((4x,4x+2)\) can be bundled together, as well as \((4x+1,4x+3)\), so we have about \(4\) cases.

The most complex of them is the case where \(i\) and \(j\) are both \((4x+1,4x+3)\). In this case, we additionally have to solve the following subproblem.

• Given integers \(C\), \(D\), and \(W\), count pairs \((c,d)\) such that \(0 \leq c < C, 0 \leq d < D, c \oplus d = W\).

This can be solved fast by bit DP or memoized recursion.

Implementation of the above solves the problem in \(O(poly(\log \max(R,V)))\) time.

Sample Solution (c++)