C++ คิวรีบน XOR ของ XORs ของทุก Subarray

เพื่อคำนวณ XOR ของทุก subarray ที่มีอยู่ในช่วงที่กำหนดและพิมพ์มัน ตัวอย่างเช่น:

Input : arr[] = { 4, 1, 2, 3, 5 }, Q = 3
Queries q1 = { 1, 2 }
q2 = { 2, 4 }
q3 = { 1, 4 }
Output : 0 2 0
คำอธิบาย : ตามที่ปัญหากำหนดว่าเราต้องหา XOR ของทุก subarray ในช่วงที่กำหนด ดังนั้นสำหรับ query 2 subarrays คือ: {1}, {2}, {3}, {1, 2}, {2, 3}, (1, 2, 3}
ดังนั้นคุณเห็นได้ว่าจำนวนครั้งที่องค์ประกอบปรากฏคือ:
1 ปรากฏ 3 ครั้ง
2 ปรากฏ 4 ครั้ง
3 ปรากฏ 3 ครั้ง
ตอนนี้เรารู้ว่าคุณสมบัติของ XOR คือ ตัวเลขที่ปรากฏจำนวนครั้งที่เป็นเลขคู่จะถูกตัดกันออกไป ดังนั้น 2 ถูกตัดออก และเหลือแค่ XOR ของ 3 และ 1 ซึ่งเป็นคำตอบของเรา

เราต้องสังเกตรูปแบบที่เกิดขึ้นในปัญหานี้ และนำไปใช้ตามนั้น

วิธีการหาคำตอบ

ในปัญหานี้ เราพยายามหา pattern ระหว่างที่มีอยู่ในปัญหา เมื่อเราเห็น pattern นั้น เรานำไปใช้ตามนั้นและตรวจสอบผลลัพธ์

ตัวอย่าง

โค้ด C++ สำหรับวิธีข้างต้น

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

void ansQueries(int prefeven[], int prefodd[], int l, int r){
    if ((r - l + 1) % 2 == 0) // ถ้าจำนวนองค์ประกอบในช่วงเป็นเลขคู่
        cout << "0";
    else{
        if (l % 2 == 0) // ถ้า l เป็นเลขคู่
            cout << (prefeven[r] ^ prefeven[l - 1]) << "\n";
        else // ถ้า l เป็นเลขคี่
            cout << (prefodd[r] ^ prefodd[l - 1]) << "\n";
    }
}

int main(){
    int arr[] = {4, 1, 2, 3, 5};
    int n = sizeof(arr) / sizeof(int); // ขนาดของอาร์เรย์
    int l[] = {1, 2, 1}; // ดัชนีซ้ายของคิวรีที่กำหนด
    int r[] = {2, 4, 4}; // ดัชนีขวาของคิวรีที่กำหนด
    int q = sizeof(l) / sizeof(int); // จำนวนคิวรีที่ถาม
    int prefodd[n] = {0}, prefeven[n] = {0}; // prefix xor แยกสำหรับดัชนีคู่และคี่
    for (int i = 1; i <= n; i++){
        if ((i) % 2 == 0){ // ถ้า i เป็นคู่ เราเปลี่ยน prefeven
            prefeven[i] = arr[i - 1] ^ prefeven[i - 1];
            prefodd[i] = prefodd[i - 1];
        }else{
            prefeven[i] = prefeven[i - 1];
            prefodd[i] = prefodd[i - 1] ^ arr[i - 1];
        }
    }
    for (int i = 0; i < q; i++){
        ansQueries(prefeven, prefodd, l[i], r[i]);
    }
    return 0;
}

ผลลัพธ์

0 2 0

คำอธิบายโค้ด

ในวิธีนี้ เราสังเกตก่อนว่าถ้าขนาดของช่วงของเราเป็นเลขคู่ คำตอบของเราจะเป็นศูนย์ เพราะทุกตัวเลขปรากฏจำนวนครั้งที่เป็นเลขคู่เมื่อเราพิมพ์ subarray ทั้งหมด ดังนั้นการนำ XOR ของพวกเขาจะได้คำตอบเป็น 0 ตอนนี้สำหรับส่วนต่อไปที่ขนาดของช่วงเป็นเลขคี่ ในกรณีนี้ ตัวเลขที่ปรากฏจำนวนครั้งที่เป็นเลขคี่จะอยู่ในตำแหน่งคู่ในช่วงที่กำหนด และคำตอบของเราจะเป็น XOR ของตัวเลขที่ปรากฏในตำแหน่งคู่ในช่วงที่กำหนด สองอัน เราสร้าง prefix arrays สองอันที่มี XOR ของตำแหน่งสลับกัน prefeven มี XOR ของดัชนีคู่ทั้งหมด และ prefodd มี XOR ของดัชนีคี่ทั้งหมด ตอนนี้เมื่อเราแก้คิวรี เราเพียงแค่ต้องตรวจสอบว่า l ของเราเป็นคู่หรือคี่ และให้คำตอบตามนั้น

สรุป

ในบทช่วยสอนนี้ เราแก้ปัญหา Queries on XOR of XORs of all subarrays เรายังเรียนรู้โปรแกรม C++ สำหรับปัญหานี้และวิธีการแก้ปัญหาแบบเต็มรูปแบบ (ปกติ) ที่เราใช้แก้ปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, Java, Python และภาษาอื่นๆ ได้ เราหวังว่าบทช่วยสอนนี้จะเป็นประโยชน์