E. XOR and Favorite Number 莫队 2038: [2009国家集训队]小Z的袜子(hose)

一直都说学莫队，直到现在才学，训练的时候就跪了   T_T，其实挺简单的感觉。其实训练的时候也看懂了，一知半解，就想着先敲。（其实这样是不好的，应该弄懂再敲，以后要养成这个习惯）

前缀异或也很快想出来，结果没弄好边界，也是对前缀异或和莫队的不熟练。

CF 的E题，给定区间中有多少子区间个数异或等于k

容易想到的是预处理前缀异或值，求解区间[L, R]的贡献，相当于在前缀异或值[L - 1, R]中任取两个数，异或值等于k

知道区间[L, R]的贡献，可以O(1)知道[L - 1, R]和[L, R + 1]的贡献，就可以用莫队了

把询问分块，每块大小sqrtn，然后块内按右端点排序，然后two pointer维护即可。

因为块内的大小是sqrtn，然后每次移动只会移动sqrtn的大小。复杂度是nsqrtn

两题都是莫队的一个应用，离线查询区间

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
const int maxn = 3000000 + 20;
struct Query {
    int L, R, id;
}node[maxn];
int a[maxn];
int n, m, k, magic;
bool cmp(struct Query a, struct Query b) {
    if (a.L/magic != b.L/magic) return a.L/magic < b.L/magic;
    else return a.R < b.R;
}
LL ans[maxn];
LL num[maxn];
void calc() {
    LL temp = 0;
    int L = 1, R = 0;
    num[0] = 1;
    for (int i = 1; i <= m; ++i) {
        while (R < node[i].R) {
            ++R;
            temp += num[a[R] ^ k];
            num[a[R]]++;
        }
        while (R > node[i].R) { // differ sqrt
            num[a[R]]--;
            temp -= num[a[R] ^ k];
            --R;
        }
        while (L < node[i].L) {
            num[a[L - 1]]--;
            temp -= num[a[L - 1] ^ k];
            ++L;
        }
        while (L > node[i].L) {
            --L;
            temp += num[a[L - 1] ^ k];
            num[a[L - 1]]++;
        }
        ans[node[i].id] = temp;
    }
}
void work() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
        a[i] ^= a[i - 1];
//        printf("%d  ", a[i]);
    }
    magic = (int)sqrt(n);
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &node[i].L, &node[i].R);
        node[i].id = i;
    }
    sort(node + 1, node + 1 + m, cmp);
    calc();
    for (int i = 1; i <= m; ++i) {
        cout << ans[i] << endl;
    }
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    work();
    return 0;
}

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
const int maxn = 5e5 + 20;
struct Query {
    int L, R, id;
    LL a, b;
    void init() {
        if (a != 0) {
            LL t = __gcd(a, b);
            a /= t, b /= t;
        } else b = 1;
    }
}node[maxn], ans[maxn];
int n, m, magic;
int a[maxn];
LL num[maxn];
bool cmp(struct Query a, struct Query b) {
    if (a.L/magic != b.L/magic) return a.L/magic < b.L/magic;
    else return a.R < b.R;
}
void work() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
    }
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &node[i].L, &node[i].R);
        node[i].id = i;
    }
    magic = sqrt(n);
    sort(node + 1, node + 1 + m, cmp);
    int L = 1, R = 0;
    LL res = 0;
    for (int i = 1; i <= m; ++i) {
        while (R < node[i].R) {
            ++R;
            res -= num[a[R]] * num[a[R]] - num[a[R]];
            num[a[R]]++;
            res += num[a[R]] * num[a[R]] - num[a[R]];
        }
        while (R > node[i].R) { //不同块之间才会出现
            res -= num[a[R]] * num[a[R]] - num[a[R]];
            num[a[R]]--;
            res += num[a[R]] * num[a[R]] - num[a[R]];
            R--;
        }
        while (L < node[i].L) { //每个块之间只是按照R排序的
            res -= num[a[L]] * num[a[L]] - num[a[L]];
            num[a[L]]--;
            res += num[a[L]] * num[a[L]] - num[a[L]];
            L++;
        }
        while (L > node[i].L) {
            --L;
            res -= num[a[L]] * num[a[L]] - num[a[L]];
            num[a[L]]++;
            res += num[a[L]] * num[a[L]] - num[a[L]];
        }
        ans[node[i].id].a = res, ans[node[i].id].b = 1LL * (node[i].R - node[i].L + 1) * (node[i].R - node[i].L);
    }
    for (int i = 1; i <= m; ++i) {
        ans[i].init();
        printf("%lld/%lld
", ans[i].a, ans[i].b);
    }
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    work();
    return 0;
}