# Codeforces Round #340 (Div. 2): E. XOR and Favorite Number

,

http://codeforces.com/contest/617/problem/E

Mo’s algorithmの練習。方針はすぐだったが細部がつらかった。

## solution

Mo’s algorithm。$O((N+M)\sqrt{N})$で空間$O(\max \{ k, \max a_i \})$。

## implementation

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;
int main() {
// input
int n, m, k; cin >> n >> m >> k;
vector<int> a(n); repeat (i,n) cin >> a[i];
vector<int> l(m), r(m); repeat (i,m) { cin >> l[i] >> r[i]; -- l[i]; }
// solve
//   Mo's algorithm
int sqrt_n = sqrt(n);
vector<int> ixs(m);
whole(iota, ixs, 0);
whole(sort, ixs, [&](int i, int j) {
return make_pair(l[i] / sqrt_n, r[i]) < make_pair(l[j] / sqrt_n, r[j]);
});
vector<int> acc { 0 }; whole(partial_sum, a, back_inserter(acc), bit_xor<int>());
vector<int> accs(max(k, *whole(max_element, a)) * 2 + 3);
ll cnt = 0;
int l_cur = 0, r_cur = 0;
vector<ll> ans(m);
for (int i : ixs) {
while (l[i] < l_cur) {
int i = -- l_cur;
if ((acc[i] ^ acc[r_cur]) == k) cnt += 1;
cnt += accs[acc[i] ^ k];
accs[acc[i]] += 1;
}
while (r_cur < r[i]) {
int i = r_cur ++;
accs[acc[i]] += 1;
cnt += accs[acc[i+1] ^ k];
}
while (l_cur < l[i]) {
int i = l_cur ++;
accs[acc[i]] -= 1;
cnt -= accs[acc[i] ^ k];
if ((acc[i] ^ acc[r_cur]) == k) cnt -= 1;
}
while (r[i] < r_cur) {
int i = -- r_cur;
cnt -= accs[acc[i+1] ^ k];
accs[acc[i]] -= 1;
}
ans[i] = cnt;
}
// output
repeat (i,m) {
cout << ans[i] << endl;
}
return 0;
}