CF617E XOR and Favorite Number

同洛谷P4462 [CQOI2018]异或序列 - 题目链接

定义异或运算的符号为$\oplus$，考虑对原序列求一个前缀异或，然后询问变成了有多少点对满足$a_x \oplus a_y = k$，其中$x\in [l - 1, r - 1], y\in [l, r]$

如果$a_x \oplus a_y = k$，那么$a_x = a_y \oplus k$，于是另外开一个数组$b$存$a_y \oplus k$的值，问题变成多次询问一段区间内有多少对$(x, y)$使得$a_x = b_y, x \leq y$

莫队即可，复杂度$O(n^{3 / 2})$

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 2e6 + 10, inf = 0x3f3f3f3f;

const long long Linf = 0x3f3f3f3f3f3f3f3f;

inline int read() {
    bool sym = 0; int res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}

struct QRY{int l, r, id;}qry[N];

int n, m, l[N], r[N], Q, a[N], b[N], bel[N], cnta[N], cntb[N];

long long ans[N];

void init() {
    int S = sqrt(n);
    for (int i = 1; i <= n; i += S) {
        l[++Q] = i; r[Q] = i + S - 1;
    }
    for (int i = 1; i <= Q; i++) {
        for (int j = l[i]; j <= r[i]; j++) bel[j] = i;
    }
}

bool cmp(QRY a, QRY b) {return bel[a.l] == bel[b.l] ? a.r < b.r : a.l < b.l;}

int main() {
    n = read(); m = read(); init(); int t = read();
    for (int i = 1; i <= n; i++) a[i] = read() ^ a[i - 1];
    for (int i = 1; i <= n; i++) b[i] = a[i - 1] ^ t;
    for (int i = 1; i <= m; i++) qry[i] = (QRY){read(), read(), i};
    sort(qry + 1, qry + m + 1, cmp);
    int l = 1, r = 0; long long res = 0;
    for (int i = 1; i <= m; i++) {
        while (l < qry[i].l) res -= cnta[b[l]], cnta[a[l]]--, cntb[b[l]]--, l++;
        while (l > qry[i].l) l--, cnta[a[l]]++, cntb[b[l]]++, res += cnta[b[l]];
        while (r < qry[i].r) r++, cnta[a[r]]++, cntb[b[r]]++, res += cntb[a[r]];
        while (r > qry[i].r) res -= cntb[a[r]], cnta[a[r]]--, cntb[b[r]]--, r--;
        ans[qry[i].id] = res;
    }
    for (int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
    return 0;
}