here is my O(1) solution

#include <bits/stdc++.h>
using namespace std;

long long G(long long x){
    long long a = x % 8;
    if(a == 0 || a == 1) return x;
    if(a == 2 || a == 3) return 2;
    if(a == 4 || a == 5) return x+2;
    if(a == 6 || a == 7) return 0;
    return 0;
}

int main(){
    int q;
    cin >> q;
    while(q--){
        long long l, r, ans;
        cin >> l >> r;
        ans = G(r)^G(l-1);
        cout << ans << endl;
    }
    return 0;
}

Sometimes i feel reference solutions are more confusing and its better to design your own solution once you understand what's going on.

My O(1) solution: From the index range [L, R], ignore all consecutive groups of 8 indices starting at the first multiple of 4. Then simply XOR the array values for the remaining indices. This is because each such group of 8 values will XOR to 0. The array value for an index i can be found using the following:

i%4 == 0, then a[i] = i
i%4 == 1, then a[i] = 1
i%4 == 2, then a[i] = i+1
i%4 == 3, then a[i] = 0

Example: The first few array values go like this
0 1 3 0 4 1 7 0 8 1 11 0 12 1 15 0 16 1 19 0 20 1 23 0

For the above range, L = 5, R = 18, we skip the values in italics and just XOR the remaining i.e. 1, 7, 0, 16, 1, 19

This has been one of my favorite questions on this site. It's all about the properties of XOR and finding patterns. Feels great after solving it.

Have been strugling with this question for a while, and suddenly it hit me how simple it is. Try to extend given list of array and find pattern in it, that's all it requires.