XOR ของตัวเลขที่ปรากฏจำนวนครั้งคู่ในช่วงที่กำหนด (C++)

โจทย์

ได้รับอาร์เรย์ขนาด n และ queries หลายช่วง [L, R] ต้องการหา XOR ขององค์ประกอบที่ปรากฏ จำนวนครั้งคู่ (even number of times) ในช่วงนั้น

ตัวอย่าง

array = {1, 2, 3, 1, 1, 2, 2, 3}
queries = 2
[2, 4] -> elements: 3,1,1 -> 1 appears 2 times, 3 appears 1 time -> XOR of even freq = 1
[2, 7] -> elements: 3,1,1,2,2,3 -> 1:2, 2:2, 3:2 -> XOR = 1^2^3 = 0

วิธีแก้ปัญหา (Advanced)

ใช้ BIT (Binary Indexed Tree / Fenwick Tree) ร่วมกับ Prefix XOR และ Offline Query Processing (Mo's algorithm style)

แนวคิดหลัก:

1. Prefix XOR: XOR ของช่วง [L,R] = prefixXOR[R] ^ prefixXOR[L-1]
2. Distinct XOR: XOR ของค่าที่ distinct (ไม่ซ้ำ) ในช่วง [L,R]
3. Even frequency XOR = All XOR ^ Distinct XOR (เพราะค่าที่ปรากฏคี่ครั้งจะถูก cancel ไปใน Distinct XOR)

โค้ดตัวอย่าง

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

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

bool cmp(Query a, Query b) {
    if (a.R != b.R) return a.R < b.R;
    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, Query 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] ^ (queries[i].L > 0 ? prefixXOR[queries[i].L - 1] : 0);
        int distinctXOR = findXORSum(BIT, queries[i].R) ^ (queries[i].L > 0 ? findXORSum(BIT, queries[i].L - 1) : 0);
        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);
    
    Query queries[4];
    queries[0] = {1, 4, 0};
    queries[1] = {2, 7, 1};
    queries[2] = {0, 3, 2};
    queries[3] = {3, 6, 3};
    int Q = 4;
    
    cout << "Xor sum for all queries is:\n";
    findXORSolution(arr, N, queries, Q, BIT);
    return 0;
}

ผลลัพธ์

Xor sum for all queries is:
3
2
0
2

Complexity

• Time: O((N + Q) log N) - เรียง queries + BIT operations
• Space: O(N) - BIT, prefixXOR, lastOcc arrays

สรุป

โจทย์นี้เป็น advanced range query problem ใช้เทคนิค Offline processing + BIT + XOR properties การเข้าใจความสัมพันธ์: EvenFreqXOR = AllXOR ^ DistinctXOR เป็นหัวใจสำคัญของการแก้ปัญหา