Количество подмассивов в диапазоне [L, R], имеющих XOR + 1, равное XOR (XOR) 1 для M запросов

Дан массив, arr[] из N положительных целых чисел и M запросов, состоящих из двух целых чисел [L _i , R _i ], где 1 ≤ Li ≤ Ri ≤ N . Для каждого запроса найдите количество подмассивов в диапазоне [L _i , R _i ], для которых (X+1)=(X⊕1), где X обозначает xor подмассива.

Input: arr[]= {1, 2, 9, 8, 7}, queries[] = {{1, 5}, {3, 4}}
Output: 6 1
Explanation: 
Query 1: L=1, R=5: subarrays [1, 3], [1, 4], [2, 2], [2, 5], [3, 5], [4, 4]
Query 2: L=3, R=4: subarray [4, 4]

Input: arr[] = {1, 2, 2, 4, 5}, queries[] = {{2, 4}, {3, 5}}
Output: 6 3

Наивный подход: для каждого запроса выберите заданный диапазон [L _i , R _i ] и для каждого подмассива проверьте, удовлетворяет ли он заданному условию.
Временная сложность: O(N ³ * M)

Эффективный подход: в приведенной выше задаче можно сделать следующие наблюдения:

• Чтобы удовлетворить данному условию, X должно быть четным числом, потому что
  • Если X четно, ( X ⊕1)=( X +1)
  • Если X нечетно, ( X ⊕1)=( X −1)
• Для подмассива его xor будет четным, если количество нечетных чисел в этом подмассиве четно.
• Если количество нечетных чисел четное, то сумма подмассива будет четной. Итак, подмассивы с четной суммой являются ответом на эту проблему.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N+M)
Вспомогательное пространство: O(N+M)