คิวรีสำหรับ Bitwise OR ในช่วงดัชนี [L, R] ของอาร์เรย์ที่กำหนด ใช้ C++

ในบทความนี้ เราได้รับอาร์เรย์ของจำนวนเต็ม เราถูกมอบหมายให้หา bitwise OR ของตัวเลขทั้งหมดที่อยู่ในช่วงที่กำหนด ตัวอย่างเช่น:

Input: arr[] = {1, 3, 1, 2, 3, 4}, q[] = {{0, 1}, {3, 5}}
Output: 3 7
1 OR 3 = 3
2 OR 3 OR 4 = 7

Input: arr[] = {1, 2, 3, 4, 5}, q[] = {{0, 4}, {1, 3}}
Output: 7 7

ในปัญหาที่กำหนด เราจะเข้าแก้ด้วยวิธี Brute Force ก่อน แล้วตรวจสอบว่ามันสามารถทำงานกับข้อจำกัดที่สูงกว่าได้หรือไม่ ถ้าไม่ได้ เราจะเพิ่มประสิทธิภาพวิธีการของเราให้ทำงานกับข้อจำกัดที่สูงกว่าได้เช่นกัน

วิธี Brute Force

ในวิธีนี้ เราจะเพียงแค่เดินทางผ่านแต่ละช่วงและคำนวณ bitwise OR ของตัวเลขทั้งหมดในช่วงนั้นและพิมพ์คำตอบของเรา

ตัวอย่าง

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

int main() {
    int arr[] = { 7, 5, 3, 5, 2, 3 };
    int n = sizeof(arr) / sizeof(int); // ขนาดของอาร์เรย์
    int queries[][2] = { { 1, 3 }, { 4, 5 } }; // คิวรีที่กำหนด
    int q = sizeof(queries) / sizeof(queries[0]); // จำนวนคิวรี
    
    for(int i = 0; i < q; i++) { // เดินทางผ่านคิวรีทั้งหมด
        long ans = 0;
        for(int j = queries[i][0]; j <= queries[i][1]; j++) // เดินทางผ่านช่วง
            ans |= arr[j]; // คำนวณคำตอบ
        cout << ans << "\n";
    }
    return 0;
}

ผลลัพธ์

7 3

วิธีนี้มีความซับซ้อนด้านเวลา O(N×Q) โดยที่ N คือขนาดของอาร์เรย์ และ Q คือจำนวนคิวรี ตอนนี้คุณเห็นได้ว่าความซับซ้อนนี้จะไม่ทำงานกับข้อจำกัดที่สูงกว่า ดังนั้นตอนนี้เราจะเพิ่มประสิทธิภาพวิธีการของเราให้ทำงานกับข้อจำกัดที่สูงกว่าได้เช่นกัน

วิธีที่มีประสิทธิภาพ (Efficient Approach)

ในวิธีนี้ เราจะคำนวณ prefix bits count แล้วเราจะตรวจสอบว่าตัวเลขใดตัวเลขหนึ่งมี bit เฉพาะเจาะจงตั้งค่าไว้ ถ้ามี เราจะใส่ bit นี้ในคำตอบ ไม่เช่นนั้น เราจะเว้น bit นั้นไว้

ตัวอย่าง

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

#define bitt 32
#define MAX (int)10e5
int prefixbits[bitt][MAX];

void bitcount(int *arr, int n) { // สร้าง prefix counts
    for (int j = 31; j >= 0; j--) {
        prefixbits[j][0] = ((arr[0] >> j) & 1);
        for (int i = 1; i < n; i++) {
            prefixbits[j][i] = arr[i] & (1LL << j);
            prefixbits[j][i] += prefixbits[j][i - 1];
        }
    }
    return;
}

int check(int l, int r) { // คำนวณคำตอบ
    long ans = 0; // เพื่อหลีกเลี่ยง overflow เราใช้ long
    for (int i = 0; i < 32; i++) {
        int x;
        if (l == 0)
            x = prefixbits[i][r];
        else
            x = prefixbits[i][r] - prefixbits[i][l - 1];
        if (x != 0)
            ans = (ans | (1LL << i));
    }
    return ans;
}

int main() {
    int arr[] = {7, 5, 3, 5, 2, 3};
    int n = sizeof(arr) / sizeof(int); // ขนาดของอาร์เรย์
    bitcount(arr, n);
    int queries[][2] = {{1, 3}, {4, 5}}; // คิวรีที่กำหนด
    int q = sizeof(queries) / sizeof(queries[0]); // จำนวนคิวรี
    
    for (int i = 0; i < q; i++) {
        cout << check(queries[i][0], queries[i][1]) << "\n";
    }
    return 0;
}

ผลลัพธ์

7 3

วิธีนี้มีความซับซ้อนด้านเวลา O(N) โดยที่ N คือขนาดของอาร์เรย์ ดังนั้นวิธีนี้จึงสามารถทำงานกับข้อจำกัดที่สูงกว่าได้

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

ในวิธีนี้ เราคำนวณ prefix bits count และเก็บไว้ ตอนนี้เราคำนวณคิวรี เราเดินทางผ่าน prefix count นั้นและลบ bit counts ของ l-1 ทำให้เรามี counts ของ bit ของตัวเลขในช่วง [l, r] ตอนนี้เรารู้แล้วว่าถ้า bit ตั้งค่าไว้ในตัวเลขใดตัวเลขหนึ่ง ถ้าคุณเอามา bitwise OR กับตัวเลขอื่น bit นั้นจะยังคงตั้งค่าไว้ ดังนั้นเราใช้คุณสมบัตินี้ของ bitwise OR เราตรวจสอบว่าจำนวน bit ไม่เป็นศูนย์ หมายความว่ามีตัวเลขที่มี bit ตั้งค่าไว้อยู่ในช่วง ดังนั้นเราตั้งค่า bit นั้นของคำตอบและดำเนินการต่อผ่านลูป และสุดท้ายพิมพ์คำตอบ

สรุป

บทความนี้แก้ปัญหาการคำนวณ Queries สำหรับ bitwise OR ในช่วงดัชนี [L, R] ของอาร์เรย์ที่กำหนด เรายังเรียนรู้โปรแกรม C++ สำหรับปัญหานี้และวิธีการแก้ปัญหาแบบเต็มรูปแบบ (ธรรมดาและมีประสิทธิภาพ) ที่เราใช้แก้ปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, Java, Python และภาษาอื่นๆ ได้ เราหวังว่าบทความนี้จะเป็นประโยชน์