P4462「[CQOI2018]异或序列」

4 5 1
1 2 3 1
1 4
1 3
2 3
2 4
4 4

4
2
1
2
1

#include<bits/stdc++.h>
using namespace std;

#ifndef _MOBK_
#define _MOBK_
#define ll long long
#define il inline
#define re register
#define MAXN 200100

char buf[200];

il ll read() {
    ll x = 0;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x;
}

il void write(ll x) {
    ll cnt = 0;
    while(x || !cnt) {
        buf[cnt++] = (x%10) + 48;
        x /= 10;
    }
    while(cnt) {
        putchar(buf[--cnt]);
    }
    putchar('\n');
}

// 分块大小
ll bz;
// 莫队
struct MOBK {
    // 查询区间
    struct Query {
        ll l, r, idx;
        bool operator < (const Query q) const {
            return l/bz != q.l/bz ? l < q.l : 
                (l/bz) & 1 ? r < q.r : r > q.r;
        }
    };
    ll n, m;            // 数列长度，查询次数
    ll curans;          // 当前查询答案
    ll count[MAXN];     // 计数数组
    ll result[MAXN];    // 答案数组（具体问题具体分析）
    Query query[MAXN];  // 查询区间数组
    // 初始化
    MOBK() {
        curans = 0;
        memset(count, 0, sizeof(count));
        memset(query, 0, sizeof(query));
    }
    MOBK(int _n, int _m): n(_n), m(_m) {
        bz = (ll)sqrt(n);
        curans = 0;
        memset(count, 0, sizeof(count));
        memset(query, 0, sizeof(query));
    }
    // 区间长度增一
    il void add(ll x, ll k) {
        curans += count[x^k];
        ++count[x];
    }
    // 区间长度减一
    il void del(ll x, ll k) {
        --count[x];
        curans -= count[x^k];
        
    }
    // 求解答案
    void solver(ll *a, ll k) {
        sort(query, query+m);
        re ll l = query[0].l;
        re ll r = query[0].l-1;
        for(re ll i = 0; i < m; ++i) {
            while(r < query[i].r) {
                add(a[++r], k);
            }
            while(r > query[i].r) {
                del(a[r--], k);
            }
            while(l < query[i].l) {
                del(a[l++], k);
            }
            while(l > query[i].l) {
                add(a[--l], k);
            }
            result[query[i].idx] = curans;
        }
        for(ll i = 0; i < m; ++i) {
            write(result[i]);
        }
    }
};
#endif

int main()
{
    ll n = read();
    ll m = read();
    ll k = read();
    static ll a[MAXN] = {0};
    static MOBK mobk = MOBK(n, m);
    for(re ll i = 1; i <= n; ++i) {
        a[i] = read();
    }
    for(re ll i = 2; i <= n; ++i) {
        a[i] ^= a[i-1];
    }
    for(re ll i = 0; i < m; ++i) {
        mobk.query[i].l = read() - 1;
        mobk.query[i].r = read();
        mobk.query[i].idx = i;
    }
    mobk.solver(a, k);
    return 0;
}