Mo's algorithm

/*
Koliko ima l<=i<j<=r tako da je XOR[i..j]=K
*/

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

const int N=1e5+10;
const int Q=1e6+10;
const int LIM=(1<<20)+10;
const int BLOCK_SIZE=320;
const int BLOCKS=320;

int ksor[N];
long long sol[N], tot;
int cnt[LIM];
int n, k, q;

struct Query
{
    int l, r, idx;
    bool operator<(const Query &p) const
    {
        return r<p.r;
    }
};

vector<Query> v[BLOCKS];

void add (int x)
{
    tot+=1ll*cnt[x^k];
    cnt[x]++;
}

void del (int x)
{
    cnt[x]--;
    tot-=1ll*cnt[x^k];
}

int main()
{
    scanf ("%d%d%d", &n, &q, &k);

    for (int i=1;i<=n;i++)
    {
        int a;
        scanf ("%d", &a);
        ksor[i]=ksor[i-1]^a;
    }
    for (int i=1;i<=q;i++)
    {
        Query xt=*new Query();
        xt.idx=i;
        scanf ("%d%d", &xt.l, &xt.r);
        xt.l--; xt.r++;
        v[xt.l/BLOCK_SIZE].push_back(xt);
    }

    for (int i=0;i<BLOCKS;i++) sort (v[i].begin(), v[i].end());

    for (int i=0;i<BLOCKS;i++)
    {
        int levo=i*BLOCK_SIZE;
        int desno=i*BLOCK_SIZE;

        for (auto xt: v[i])
        {
            while (desno<xt.r)
            {
                add (ksor[desno]);
                desno++;
            }
            while (levo>xt.l)
            {
                levo--;
                add (ksor[levo]);
            }
            while (levo<xt.l)
            {
                del (ksor[levo]);
                levo++;
            }

            sol[xt.idx]=tot;
        }

        for (int j=levo;j<desno;j++) del(ksor[j]);
    }

    for (int i=1;i<=q;i++) printf ("%lld\n", sol[i]);

    return 0;
}