算法

(莫队) $O(N\sqrt{Q})$

本题是莫队板题，但我不会说我调了一年

记 $S_i = a_1 \oplus a_2 \oplus \cdots \oplus a_i$

由异或的性质可知，$a_i \oplus a_{i+1} \oplus \cdots \oplus a_j = S_j \oplus S_{i-1}$
于是，原题就转化成了在区间 $[l-1, r]$ 中两个 $S_i$ 的异或值为 $k$ 的数对有多少个

对于这个问题，可以用莫队来处理！

ps：本题的数据比较弱，其实应该要开 long long

双倍经验：CF617E

C++ 代码

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

int D;
int a[100005], cnt[2000005]; ll ans[100005];
struct Q {
    int l, r, i;
    bool operator<(const Q &o) const {
        int di = l/D, dj = o.l/D;
        if (di != dj) return l < o.l;
        return r < o.r;
    }
} qs[100005];

int readint(){
    int x = 0, f = 1; 
    char c = getchar();
    while (c < '0' or c > '9') { if (c == '-') f = -1; c = getchar(); }
    while(c >= '0' and c <= '9') { x = x*10 + c-'0'; c = getchar(); }
    return x*f;
}

int main() {
    int n = readint(), q = readint(), k = readint();

    for (int i = 1; i <= n; ++i) a[i] = readint()^a[i-1];

    rep(i, q) qs[i].l = readint()-1, qs[i].r = readint();
    rep(i, q) qs[i].i = i;
    D = n/sqrt(q)+1;

    sort(qs, qs+q);

    int nl = 0, nr = -1;
    ll now = 0;
    auto add = [&](int i) {
        now += cnt[a[i]^k];
        cnt[a[i]]++;
    };
    auto del = [&](int i) {
        cnt[a[i]]--;
        now -= cnt[a[i]^k];
    };
    rep(qi, q) {
        int l = qs[qi].l, r = qs[qi].r, i = qs[qi].i;
        while (nl < l) del(nl), nl++;
        while (nl > l) nl--, add(nl);
        while (nr < r) nr++, add(nr);
        while (nr > r) del(nr), nr--;
        ans[i] = now;
    }

    rep(i, q) printf("%lld\n", ans[i]);

    return 0;
}

// 实现2：
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

int D;
int a[100005], cnt[2000005]; ll ans[100005];
struct Q {
    int l, r, i;
    bool operator<(const Q &o) const {
        int di = l/D, dj = o.l/D;
        if (di != dj) return l < o.l;
        return r < o.r;
    }
} qs[100005];

int readint(){
    int x = 0, f = 1; 
    char c = getchar();
    while (c < '0' or c > '9') { if (c == '-') f = -1; c = getchar(); }
    while(c >= '0' and c <= '9') { x = x*10 + c-'0'; c = getchar(); }
    return x*f;
}

int main() {
    int n = readint(), q = readint(), k = readint();

    for (int i = 1; i <= n; ++i) a[i] = readint()^a[i-1];

    rep(i, q) qs[i].l = readint()-1, qs[i].r = readint();
    rep(i, q) qs[i].i = i;
    D = n/sqrt(q)+1;

    sort(qs, qs+q);

    int nl = 0, nr = -1;
    ll now = 0;
    auto add = [&](int i, int x=1) {
        if (k) now -= cnt[a[i]]*cnt[a[i]^k];
        else now -= cnt[a[i]]*(cnt[a[i]]-1)/2;
        cnt[a[i]] += x;
        if (k) now += cnt[a[i]]*cnt[a[i]^k];
        else now += cnt[a[i]]*(cnt[a[i]]-1)/2;
    };
    auto del = [&](int i) {
        add(i, -1);
    };
    rep(qi, q) {
        int l = qs[qi].l, r = qs[qi].r, i = qs[qi].i;
        while (nl < l) del(nl), nl++;
        while (nl > l) nl--, add(nl);
        while (nr < r) nr++, add(nr);
        while (nr > r) del(nr), nr--;
        ans[i] = now;
    }

    rep(i, q) printf("%lld\n", ans[i]);

    return 0;
}