ในบทความนี้ เราได้รับอาร์เรย์ของจำนวนเต็ม เราได้รับมอบหมายให้ค้นหาค่าระดับบิต 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 ในปัญหาที่กำหนด เราจะเข้าใกล้มันด้วยวิธีการเดรัจฉาน จากนั้นตรวจสอบว่ามันสามารถทำงานได้สำหรับข้อจำกัดที่สูงขึ้นหรือไม่ หากไม่เป็นเช่นนั้น เราจะปรับแนวทางของเราให้เหมาะสมเพื่อทำงานกับข้อจำกัดที่สูงขึ้นเช่นกัน
แนวทางกำลังเดรัจฉาน
ในแนวทางนี้ เราจะเพียงแค่ข้ามผ่านแต่ละช่วงและคำนวณค่าระดับบิต OR ของตัวเลขทั้งหมดในช่วงนั้นและพิมพ์คำตอบของเรา
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int main() {
int arr[] = { 7, 5, 3, 5, 2, 3 };
int n = sizeof(arr) / sizeof(int); // size of our array
int queries[][2] = { { 1, 3 }, { 4, 5 } }; // given queries
int q = sizeof(queries) / sizeof(queries[0]); // number of queries
for(int i = 0; i < q; i++) { // traversing through all the queries
long ans = 0;
for(int j = queries[i][0]; j <= queries[i][1]; j++) // traversing through the range
ans |= arr[j]; // calculating the answer
cout << ans << "\n";
}
return 0;
} ผลลัพธ์
7 3
วิธีการนี้มีความซับซ้อนด้านเวลาของ O(N*Q) โดยที่ N คือขนาดของอาร์เรย์ของเรา และ Q คือจำนวนการสืบค้นข้อมูลในขณะนี้อย่างที่คุณเห็น ความซับซ้อนนี้ใช้ไม่ได้กับข้อจำกัดที่สูงกว่า ดังนั้นตอนนี้เราจะปรับแนวทางของเราให้เหมาะสม เพื่อให้ใช้ได้กับข้อจำกัดที่สูงขึ้นเช่นกัน
แนวทางที่มีประสิทธิภาพ
ในแนวทางนี้ เราจะคำนวณจำนวนบิตนำหน้า จากนั้นเราจะตรวจสอบว่าตัวเลขใดมีชุดบิตเฉพาะหรือไม่ ถ้าใช่ เราก็ใส่คำตอบนี้ลงไป อย่างอื่นเราทิ้งส่วนนี้ไว้
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
#define bitt 32
#define MAX (int)10e5
int prefixbits[bitt][MAX];
void bitcount(int *arr, int n) { // making 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) { // calculating the answer
long ans = 0; // to avoid overflow we are taking ans as 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); // size of our array
bitcount(arr, n);
int queries[][2] = {{1, 3}, {4, 5}}; // given queries
int q = sizeof(queries) / sizeof(queries[0]); // number of queries
for (int i = 0; i < q; i++) {
cout << check(queries[i][0], queries[i][1]) << "\n";
}
return 0;
} ผลลัพธ์
7 3
วิธีการนี้มีความซับซ้อนด้านเวลาของ O(N) โดยที่ N คือขนาดของอาร์เรย์ของเราเพื่อให้แนวทางนี้สามารถใช้ได้กับข้อจำกัดที่สูงกว่า
คำอธิบายของโค้ดด้านบน
ในแนวทางนี้ เรากำลังคำนวณจำนวนบิตนำหน้าและจัดเก็บไว้ ตอนนี้เราคำนวณแบบสอบถามที่เราผ่านจำนวนคำนำหน้านั้นและลบการนับบิตของ l-1 เพื่อให้เรานับบิตของตัวเลขในช่วง [l, r] ตอนนี้ที่เรารู้ถ้าบิตถูกตั้งค่าเป็นตัวเลขใด ๆ ดังนั้นหากคุณใช้ค่าบิต OR กับตัวเลขอื่น ๆ บิตจะยังคงตั้งค่าอยู่ ดังนั้นโดยใช้คุณสมบัติของบิตนี้ หรือ เราจะตรวจสอบว่าจำนวนบิตไม่ใช่ศูนย์หรือไม่ แสดงว่ามีตัวเลขที่มีชุดบิตอยู่ในช่วง ดังนั้นเราจึงตั้งค่าบิตนั้น ของคำตอบและดำเนินการวนซ้ำและสุดท้ายพิมพ์คำตอบ
บทสรุป
บทความนี้แก้ปัญหาในการคำนวณ Queries สำหรับ bitwise OR ในช่วงดัชนี [L, R] ของอาร์เรย์ที่กำหนด นอกจากนี้เรายังได้เรียนรู้โปรแกรม C ++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ ( Normal และ มีประสิทธิภาพ ) โดยที่เราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ เราหวังว่าคุณจะพบว่าบทความนี้มีประโยชน์
