수열과 쿼리 11 (백준 13704)

안녕하세요. 오늘은 누적 XOR을 할 거에요.

문제

https://www.acmicpc.net/problem/13704

아이디어

누적 XOR 배열을 만듭시다.
그리고 수열과 쿼리 7 비슷하게 풀면 됩니다.
Ai부터 Aj까지의 XOR한 값은 Aj까지 XOR한 값과 Ai-1까지 XOR한 값을 XOR해주면 됩니다.

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define ll long long
using namespace std;

ll sqrt_N;
bool cmp(pair <pair <ll, ll>, ll> A, pair <pair <ll, ll>, ll> B)
{
    if (A.first.first / sqrt_N != B.first.first / sqrt_N) return A.first.first < B.first.first;
    return A.first.second < B.first.second;
}

ll arr[101010] = { 0 }, cnt[2020202] = { 0 }, ans = 0, K;
void PLUS(ll idx)
{
    ans += cnt[arr[idx] ^ K];
    cnt[arr[idx]]++;
}
void MINUS(ll idx)
{
    cnt[arr[idx]]--;
    ans -= cnt[arr[idx] ^ K];
}

ll Ans[101010] = { 0 };
int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N, Q, i, a, b;
    vector <pair <pair <ll, ll>, ll> > v;

    cin >> N >> K; sqrt_N = sqrt(N);
    for (i = 1; i <= N; i++)
    {
        cin >> arr[i];
        arr[i] ^= arr[i - 1];
    }

    cin >> Q;
    for (i = 1; i <= Q; i++)
    {
        cin >> a >> b;
        v.push_back({ {a - 1,b},i });
    }
    sort(v.begin(), v.end(), cmp);

    ll s = 1, e = 1; PLUS(1);
    for (i = 0; i < Q; i++)
    {
        pair <ll, ll> temp = v[i].first;
        while (s > temp.first) PLUS(--s);
        while (e < temp.second) PLUS(++e);
        while (s < temp.first) MINUS(s++);
        while (e > temp.second) MINUS(e--);

        Ans[v[i].second] = ans;
    }

    for (i = 1; i <= Q; i++)
        cout << Ans[i] << "\n";
}

감사합니다.