XOR các số xuất hiện chẵn lần trong khoảng cho trước C++

Trong bài toán này, cho một mảng n phần tử và một số truy vấn là khoảng từ điểm bắt đầu đến điểm kết thúc trong mảng. Nhiệm vụ là tìm XOR của các phần tử xuất hiện chẵn lần trong khoảng đó.

Ví dụ:

Input –

mảng = {1, 2, 3, 1, 1, 2, 2, 3}
truy vấn = 2
L=2, R=4
L=2, R=7

Output –

0
1
0

Giải pháp: tìm XOR của tất cả phần tử trong khoảng cho mỗi truy vấn. Dùng prefix XOR sum.

Ví dụ minh họa

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

struct que {
    int L, R, idx;
};

bool cmp(que a, que b) {
    if (a.R != b.R)
        return a.R < b.R;
    else
        return a.L < b.L;
}

int findXORSum(int BIT[], int index) {
    int xorSum = 0;
    index = index + 1;
    while (index > 0) {
        xorSum ^= BIT[index];
        index -= index & (-index);
    }
    return xorSum;
}

void updateBIT(int BIT[], int N, int index, int val) {
    index = index + 1;
    while (index <= N) {
        BIT[index] ^= val;
        index += index & (-index);
    }
}

int* createBitTree(int arr[], int N) {
    int* BIT = new int[N + 1];
    for (int i = 1; i <= N; i++)
        BIT[i] = 0;
    return BIT;
}

void findXORSolution(int arr[], int N, que queries[], int Q, int BIT[]) {
    int* prefixXOR = new int[N + 1];
    map<int, int> XORval;
    
    for (int i = 0; i < N; i++) {
        if (!XORval[arr[i]])
            XORval[arr[i]] = i;
        if (i == 0)
            prefixXOR[i] = arr[i];
        else
            prefixXOR[i] = prefixXOR[i - 1] ^ arr[i];
    }
    
    int lastOcc[1000001];
    memset(lastOcc, -1, sizeof(lastOcc));
    
    sort(queries, queries + Q, cmp);
    
    int res[Q];
    int j = 0;
    
    for (int i = 0; i < Q; i++) {
        while (j <= queries[i].R) {
            if (lastOcc[XORval[arr[j]]] != -1)
                updateBIT(BIT, N, lastOcc[XORval[arr[j]]], arr[j]);
            updateBIT(BIT, N, j, arr[j]);
            lastOcc[XORval[arr[j]]] = j;
            j++;
        }
        
        int allXOR = prefixXOR[queries[i].R] ^ prefixXOR[queries[i].L - 1];
        int distinctXOR = findXORSum(BIT, queries[i].R) ^ findXORSum(BIT, queries[i].L - 1);
        res[queries[i].idx] = allXOR ^ distinctXOR;
    }
    
    for (int i = 0; i < Q; i++)
        cout << res[i] << endl;
}

int main() {
    int arr[] = {1, 2, 1, 1, 2, 2, 3, 1, 3};
    int N = sizeof(arr) / sizeof(arr[0]);
    int* BIT = createBitTree(arr, N);
    
    que queries[4];
    queries[0].L = 1; queries[0].R = 4; queries[0].idx = 0;
    queries[1].L = 2; queries[1].R = 7; queries[1].idx = 1;
    queries[2].L = 0; queries[2].R = 3; queries[2].idx = 2;
    queries[3].L = 3; queries[3].R = 6; queries[3].idx = 3;
    
    int Q = sizeof(queries) / sizeof(queries[0]);
    
    cout << "XOR cho tất cả truy vấn:\n";
    findXORSolution(arr, N, queries, Q, BIT);
    
    return 0;
}

Kết quả

XOR cho tất cả truy vấn:
3
2
0
2