Moes_algo.cpp

#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <set>
#include <cassert>
#include <map>
#include <ctime>
#include <cstdlib>
#include <unordered_map>
#include <random>
#include <deque>

using namespace std;

#define pii pair <int, int>

int pref[100000];
int a[100000];
int arr[1000001];
int res[100000];
const int sz = 333;

vector <pair <pii, int> > q;

bool cmp(pair <pii, int> a, pair <pii, int> b)
{
	if (a.first.first / sz != b.first.first / sz)
		return a.first.first < b.first.first;
	return a.first.second < b.first.second;
}

int main()
{
	::ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n, m, k;
	int x;
	cin >> n >> m >> k;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	pref[0] = 0;
	for (int i = 1; i <= n; i++)
		pref[i] = a[i - 1] ^ pref[i - 1];

	for (int i = 0; i < m; i++)
	{
		int l, r;
		cin >> l >> r;
		--l, --r;
		q.push_back(make_pair(pii(l, r), i));
	}
	sort(q.begin(), q.end(), cmp);
	int curl = 0, curr = n + 1; //curr isn't in our thing
	long long result = 0;
	int block = -1;
	for (int i = 0; i < m; i++)
	{
		if (q[i].first.first / sz != block)
		{
			block = q[i].first.first / sz;
			memset(arr, 0, sizeof(arr));
			curl = q[i].first.first;
			arr[pref[curl]]++;
			curr = curl;
			result = 0;
		}
		while (curr <= q[i].first.second)
		{
			int z = pref[curr + 1] ^ k;
			result += arr[z];
			arr[pref[curr + 1]]++;
			curr++;
		}
		while (curl > q[i].first.first) //(l, r)
		{
			//should add elements these have xor with pref[curl - 1] equal to k
			int z = pref[curl - 1] ^ k;
			result += arr[z];
			arr[pref[curl - 1]]++;
			curl--;
		}
		while (curl < q[i].first.first)
		{
			//should remove elements these have xor with pref[curl] equal to k
			int z = pref[curl] ^ k;
			result -= arr[z];
			arr[pref[curl]]--;
			curl++;
		}
		res[q[i].second] = result;
	}

	for (int i = 0; i < m; i++)
		cout << res[i] << endl;
	
	return 0;
}