1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
|
using namespace std;
int n, m, k, sz; const int maxn = 1e5 + 5;
struct { int l, r, id, pos; bool operator <(const node &x)const{ return pos != x.pos ? l < x.l : (pos & 1) ? r < x.r : r > x.r; } }q[maxn];
int a[maxn]; typedef long long ll; ll cnt[maxn * 20]; ll ans[maxn]; ll res;
void add(int x){ res += cnt[a[x] ^ k]; cnt[a[x]]++; }
void del(int x){ cnt[a[x]]--; res -= cnt[a[x] ^ k]; }
int main(){ ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); cin >> n >> m >> k; sz = sqrt(n); for(int i = 1; i <= n; i++) cin >> a[i], a[i] ^= a[i - 1]; for(int i = 1; i <= m; i++) cin >> q[i].l >> q[i].r, q[i].id = i, q[i].pos = q[i].l / sz; sort(q + 1, q + m + 1); int l = 1, r = 0; cnt[0] = 1; res = 0; for(int i = 1; i <= m; i++){ while(l < q[i].l) del(l - 1), l++; while(l > q[i].l) l--, add(l - 1); while(r > q[i].r) del(r) , r--; while(r < q[i].r) r++, add(r); ans[q[i].id] = res; } for(int i = 1; i <= m; i++) cout << ans[i] << 'n'; return 0; }
|
近期评论