Code : A BIT of an Inequality

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

const int mb = 30;

long long solve(vector<int> &a) {
    int n = a.size();
    vector<int> pref = a;
    for (int i = 1; i < n; i++) {
        pref[i] ^= pref[i - 1];
    }

    auto query = [&](int i, int j) { return pref[j] ^ (i ? pref[i - 1] : 0); };

    long long ans = 0;
    for (int x = 0; x < n; x++) {
        for (int z = x; z < n; z++) {
            for (int y = x; y <= z; y++) {
                if ((query(x, y) ^ query(y, z)) > query(x, z)) {
                    ans++;
                }
            }
        }
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        cout << solve(a) << "\n";
    }
    return 0;
}

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

const int mb = 31;
bool is_bit_set(int x, int i) { return ((1 << i) & x) != 0; }

bool is_highest_set_bit(int x, int i) {
    if (!is_bit_set(x, i)) {
        return false;
    }
    x >>= (i + 1);
    return x == 0;
}

long long solve(vector<int> &a) {
    int n = a.size();
    vector<int> pref = a;
    for (int i = 1; i < n; i++) {
        pref[i] ^= pref[i - 1];
    }

    auto query = [&](int i, int j) { return pref[j] ^ (i ? pref[i - 1] : 0); };

    long long ans = 0;
    for (int x = 0; x < n; x++) {
        for (int z = x; z < n; z++) {
            int have = query(x, z);
            for (int b = 0; b < mb; b++) {
                // Count candidates where first set bit is at position b.
                int sample = (1 << b);
                if ((have ^ sample) <= have) {
                    continue;
                }

                for (int y = x; y <= z; y++) {
                    if (is_highest_set_bit(a[y], b)) {
                        ans++;
                    }
                }
            }
        }
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        cout << solve(a) << "\n";
    }
    return 0;
}

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

const int mb = 31;

bool is_bit_set(int x, int i) { return ((1 << i) & x) != 0; }

// Be careful about querying msb(0).
int msb(int n) { return n ? 31 - __builtin_clz(n) : -1; }

long long solve(vector<int> &a) {
    int n = a.size();
    vector<int> pref = a;
    for (int i = 1; i < n; i++) {
        pref[i] ^= pref[i - 1];
    }

    auto query_prefix = [&](int i, int j) {
        return pref[j] ^ (i ? pref[i - 1] : 0);
    };

    vector<vector<int>> freq(mb, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        freq[msb(a[i])][i]++;
    }
    for (int b = 0; b < mb; b++) {
        auto &vec = freq[b];
        for (int i = 1; i < n; i++) {
            vec[i] += vec[i - 1];
        }
    }

    auto query_sum = [&](int b, int i, int j) {
        auto &vec = freq[b];
        return vec[j] - (i ? vec[i - 1] : 0);
    };

    long long ans = 0;
    for (int x = 0; x < n; x++) {
        for (int z = x; z < n; z++) {
            int have = query_prefix(x, z);
            for (int b = 0; b < mb; b++) {
                // Count candidates where first set bit is at position b.
                int sample = (1 << b);
                if ((have ^ sample) <= have) {
                    continue;
                }
                ans += query_sum(b, x, z);
            }
        }
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        cout << solve(a) << "\n";
    }
    return 0;
}

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

// Be careful about querying msb(0).
int msb(int n) { return n ? 31 - __builtin_clz(n) : -1; }

long long solve(vector<int> &a) {
    int n = a.size();

    long long ans = 0;
    for (int y = 0; y < n; y++) {
        int b = msb(a[y]);
        // Remove all bits from all numbers except bits at index b.
        vector<int> backup = a;
        for (int i = 0; i < n; i++) {
            a[i] = (a[i] >> b) & 1;
        }

        map<int, int> lhs, rhs;
        int running_xor = 0;
        for (int i = y - 1; i >= 0; i--) {
            running_xor ^= a[i];
            lhs[running_xor]++;
        }

        running_xor = 0;
        for (int i = y + 1; i < n; i++) {
            running_xor ^= a[i];
            rhs[running_xor]++;
        }

        // a[i] is 1.
        // ..(1)..
        ans += lhs[1], ans += rhs[1];
        ans += lhs[0] * rhs[1];
        ans += lhs[1] * rhs[0];

        a = backup;
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        cout << solve(a) << "\n";
    }
    return 0;
}

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

const int mb = 31;

// Be careful about querying msb(0).
int msb(int n) { return n ? 31 - __builtin_clz(n) : -1; }

vector<long long> easy_version(vector<int> &a) {
    int n = a.size();

    vector<vector<long long>> pref(n, vector<long long>(2, 0));
    vector<vector<long long>> suff(n, vector<long long>(2, 0));

    pref[0][a[0]] = 1;
    for (int i = 1; i < n; i++) {
        pref[i][a[i]]++;
        for (int j = 0; j <= 1; j++) {
            pref[i][j] += pref[i - 1][j ^ a[i]];
        }
    }

    suff[n - 1][a[n - 1]] = 1;
    for (int i = n - 2; i >= 0; i--) {
        suff[i][a[i]]++;
        for (int j = 0; j <= 1; j++) {
            suff[i][j] += suff[i + 1][j ^ a[i]];
        }
    }

    auto valid = [&](int i) { return i >= 0 && i < n; };

    vector<long long> ans(n);
    for (int i = 0; i < n; i++) {
        if (a[i] == 0) {
            continue;
        }

        if (valid(i - 1)) {
            ans[i] += pref[i - 1][1];
        }
        if (valid(i + 1)) {
            ans[i] += suff[i + 1][1];
        }
        if (valid(i - 1) && valid(i + 1)) {
            ans[i] += pref[i - 1][0] * suff[i + 1][1];
            ans[i] += pref[i - 1][1] * suff[i + 1][0];
        }
    }
    return ans;
}

long long solve(vector<int> &a) {
    int n = a.size();

    vector<vector<long long>> dp(mb);
    for (int b = 0; b < mb; b++) {
        vector<int> copy(n);
        for (int i = 0; i < n; i++) {
            copy[i] = (a[i] >> b) & 1;
        }
        dp[b] = easy_version(copy);
    }

    long long ans = 0;
    for (int y = 0; y < n; y++) {
        int b = msb(a[y]);
        ans += dp[b][y];
    }
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int zz = 0; zz < t; zz++) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (int i = 0; i < n; i++) {
            cin >> a[i];
        }
        cout << solve(a) << "\n";
    }
    return 0;
}