【链接】
http://codeforces.com/problemset/problem/617/E
【题意】
给定一个数组，多次查询,问区间l,r中有多少个子区间满足区间异或为k
【思路】
查询很大，意味着每次回答的时间复杂度不能太大。对于本题，我们可以维护一个前缀异或，sum[i],区间[a,b]异或为k等价于sum[a-1]^sum[b]=k,假如我们知道了[l,r]，中有多少个子区间满足，那么可以通过异或方程的性质求出[l-1,r],[l+1,r],[l,r-1],[l,r+1]。那么我们可以离线询问，莫队算法求解。注意，c[i]表示异或为i的区间个数，c[0]=1初始化;
【代码】
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn = 1e5 + 6;
ll a[maxn];
ll ans[maxn];
ll sum[maxn];
ll c[maxn];
ll n, m, k;
ll unit;
ll tmp;struct node {ll l, r, id;
}t[maxn];ll cmp(node a, node b) {if (a.l / unit != b.l / unit)return a.l / unit < b.l / unit;return a.r < b.r;
}void add(ll id) {tmp += c[a[id] ^ k];c[a[id]]++;
}void dele(ll id) {c[a[id]]--;tmp -= c[a[id] ^ k];
}void work() {c[0] = 1;ll L = 1;ll R = 0;tmp = 0;for (ll i = 1; i <= m; i++) {while (L > t[i].l) { L--; add(L - 1); }while (L < t[i].l) { dele(L - 1); L++; }while (R > t[i].r) { dele(R); R--; }while (R < t[i].r) { R++; add(R); }ans[t[i].id] = tmp;}
}int main() {scanf("%lld%lld%lld", &n, &m, &k);for (ll i = 1; i <= n; i++)scanf("%lld", &a[i]),a[i]^=a[i-1];for (ll i = 1; i <= m; i++) {scanf("%lld%lld", &t[i].l, &t[i].r);t[i].id = i;}unit = (ll)sqrt(n);sort(t + 1, t + 1 + m, cmp);work();for (ll i = 1; i <= m; i++) {printf("%lld\n", ans[i]);}
}