617E - XOR and Favorite Number - CodeForces Solution

//#define _GLIBCXX_DEBUG
//#include <bits/stdc++.h>
#include <map>

#include <string>

#include <vector>

#include <iostream>

#include <random>

#include <algorithm>

#include <set>

#include <unordered_set>

#include <unordered_map>

#include <queue>

#define debug(x) std::cerr << (#x) << ": " << (x) << std::endl;
#define all(x) x.begin(), x.end()

//#pragma GCC target("avx2")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
//#pragma GCC optimize("unroll-loops")

using std::cin;
using std::cout;
using std::vector;
using std::string;
using ll = long long;
using ld = long double;
using pl = std::pair < ll, ll >;

struct el
{
    int first, second, id;
};

vector<ll> p;
vector<ll> cnt(2 * 1e6 + 100);
ll n, m, k;
ll tl = 0, tr = 0, ans = 0;

void fit(ll l, ll r)
{
    while (tr < r)
    {
        ans += cnt[p[tr] ^ k];
        ++cnt[p[tr]];
        ++tr;
    }

    while (tl < l)
    {
        --cnt[p[tl]];
        ans -= cnt[p[tl] ^ k];
        ++tl;
    }

    while (tl > l)
    {
        --tl;
        ans += cnt[p[tl] ^ k];
        ++cnt[p[tl]];
    }
}

ll bl = 400;
int main() {
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> k;
    vector<ll> vc(n); for (ll& i : vc)cin >> i;
    p.resize(n + 1);
    for (ll i = 0; i < n; ++i)
    {
        p[i + 1] = p[i] ^ vc[i];
    }

    vector<vector<el>> z(n / bl + 100);
    for (ll i = 0; i < m; ++i)
    {
        ll a, b; cin >> a >> b; --a; ++b;
        z[a / bl].push_back({ a,b,i });
    }

    for (vector<el>& i : z)std::sort(all(i), [](el a, el b) {return a.second < b.second; });

    vector<ll> a(m);
    for (ll i = 0; i < z.size(); ++i)
    {
        tl = 0;
        tr = 0;
        ans = 0;


        for (el& t : z[i])
        {
            fit(t.first, t.second);
            a[t.id] = ans;
        }

        if (z[i].size() == 0)continue;
        for (ll t = z[i].back().first; t < z[i].back().second; ++t)
        {
            --cnt[p[t]];
        }
    }

    for (ll& i : a)cout << i << ' ';

    return 0;
}