แบบสอบถาม C ++ บน XOR ของ XOR ของ Subarrays ทั้งหมด

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

Input : arr[] = { 4, 1, 2, 3, 5 }, Q = 3

Queries

q1 = { 1, 2 }
q2 = { 2, 4 }
q3 = { 1, 4 }

Output : 0
2
0
Explanation : As the given problem states that we need to find XOR of all the subarrays present in the given range so as for query 2 the subarrays are :
{1}, {2}, {3}, {1, 2}, {2, 3}, (1, 2, 3}
So as you can see the number of occurrences of elements are :
1 is present 3 times
2 is present 4 times
3 is present 3 times
Now as we know the property of XOR is that the numbers that are present an even number of times get canceled out so out 2 got canceled out and just the XOR of 3 and 1 remained and that was our answer.

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

แนวทางในการหาแนวทางแก้ไข

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

ตัวอย่าง

รหัส C++ สำหรับแนวทางข้างต้น

 
#include <bits/stdc++.h>
using namespace std;
void ansQueries(int prefeven[], int prefodd[], int l, int r){
    if ((r - l + 1) % 2 == 0) // if number of element present in the range is even
        cout << "0";
    else{
        if (l % 2 == 0) // if l is even
            cout << (prefeven[r] ^ prefeven[l - 1]) << "\n";
        else // if l is odd
            cout << (prefodd[r] ^ prefodd[l - 1]) << "\n";
    }
}
int main(){
    int arr[] = {4, 1, 2, 3, 5};
    int n = sizeof(arr) / sizeof(int); // size of our array
    int l[] = {1, 2, 1}; // given queries' left index
    int r[] = {2, 4, 4}; // given queries' right index
    int q = sizeof(l) / sizeof(int);         // number of queries asked
    int prefodd[n] = {0}, prefeven[n] = {0}; // different prefix xor for even and odd indices
    for (int i = 1; i <= n; i++){
        if ((i) % 2 == 0){ // if i is even then we change 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;
}

ผลลัพธ์

02
0

คำอธิบายของโค้ดด้านบน

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

บทสรุป

ในบทช่วยสอนนี้ เราแก้ปัญหาเพื่อแก้ปัญหาการสืบค้นเกี่ยวกับ XOR ของ XOR ของอาร์เรย์ย่อยทั้งหมด นอกจากนี้เรายังได้เรียนรู้โปรแกรม C ++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ ( Normal) ซึ่งเราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ เราหวังว่าคุณจะพบว่าบทช่วยสอนนี้มีประโยชน์