PROBLEM
Given an array A of non-negative integers. Answer Q queries each containing a pair of indices (l, r), find the number of pairs of indices (i, j) (where l \leq i \leq j \leq r) such that
SOLUTION
Suppose we create an array R such that R_i denotes the largest index j, such that pair [i, j] is good.
Let us fix i, we want to largest j such that range [i, j] is good. Let f_i denotes xor of first i elements of array i. We can notice that our inequality changes to f_i \oplus f_{i-1} \leq f_{i+1} \oplus f_{i-1} \leq \dots \leq f_j \oplus f_{i-1}. We process the bits of f_i in the decreasing order of signficance of bits, i.e. from highest sigificant to lowest. Let focus on the highest signficant bit of f_k \oplus f_{i-1} for k from i to j. The pattern followed by bits for valid pairs of k should be 0, 0, 0, 1, 1, 1, etc. It can’t be 0 0 0 1 1 1 0. It should be a set of zeros, followed by a set of ones. So, for each bit, starting from the sigficant bit, we maintain the largest possible valid k for each index i. Finally, F_i will be the minimum value of k over all the bits. This can be done in \mathcal{O}(N \log (max(A_i)) time.
Another way of calculating R is as follows. For each index i, we just iterate until the inequality fails, but with a small optimization of skipping zeroes. It can be proved that it takes \mathcal{O}(\log{max(A)}) time.
Persistent Segment Tree Based Solution
Let us assume l to be fixed to 1. We create an array B such that B[i] denotes the answer of query l = 1, r = i. You can create the B array in \mathcal{O}(N) time.
Now, let us go to l = 2, and see how should the new B array should be updated? i.e. what happens to the answers of queries when l = 2, r = i. Note that now the B array should not consider the pair of indices (1, j) where j \leq R_1. This is equivalent to subtracting 1 from each element in the array B from index 2 to R_1.
Similarly, when you from l = 2 to l = 3, you will be subtracting 1 from index 2 to R_2 to update the array B.
You can maintain the array B using a segment tree. The operations of subtracting 1 a range can be done using segment tree. Note that you have to answer a query [l, r] in an online manner. So, you should maintain N segment tree’s, i.e. the versions of segment tree corresponding to array B for each value of l. A query of (l, r) can be answered by finding the value of B[r] in the version of segment tree corresponding to l.
Maintaining versions of segment tree’s which is being updated can be done using persistent segment tree. Space and time complexity of this approach is \mathcal{O}(N \log{N}).