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 =  + ;

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 = ;

    int L = , R = ;

    num[] = ;

    for (int i = ; 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 - ]]--;

            temp -= num[a[L - ] ^ k];

            ++L;

        }

        while (L > node[i].L) {

            --L;

            temp += num[a[L - ] ^ k];

            num[a[L - ]]++;

        }

        ans[node[i].id] = temp;

    }

}

void work() {

    scanf("%d%d%d", &n, &m, &k);

    for (int i = ; i <= n; ++i) {

        scanf("%d", a + i);

        a[i] ^= a[i - ];

//        printf("%d  ", a[i]);

    }

    magic = (int)sqrt(n);

    for (int i = ; i <= m; ++i) {

        scanf("%d%d", &node[i].L, &node[i].R);

        node[i].id = i;

    }

    sort(node + , node +  + m, cmp);

    calc();

    for (int i = ; i <= m; ++i) {

        cout << ans[i] << endl;

    }

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    work();

    return ;

}

#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 + ;

struct Query {

    int L, R, id;

    LL a, b;

    void init() {

        if (a != ) {

            LL t = __gcd(a, b);

            a /= t, b /= t;

        } else b = ;

    }

}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 = ; i <= n; ++i) {

        scanf("%d", a + i);

    }

    for (int i = ; i <= m; ++i) {

        scanf("%d%d", &node[i].L, &node[i].R);

        node[i].id = i;

    }

    magic = sqrt(n);

    sort(node + , node +  + m, cmp);

    int L = , R = ;

    LL res = ;

    for (int i = ; 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 + ) * (node[i].R - node[i].L);

    }

    for (int i = ; i <= m; ++i) {

        ans[i].init();

        printf("%lld/%lld\n", ans[i].a, ans[i].b);

    }

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    work();

    return ;

}

巴特西

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

最新文章

热门文章