ในบทความนี้ เราได้ระบุปัญหาที่เราได้รับอาร์เรย์ของจำนวนเต็ม และเราได้รับมอบหมายให้ค้นหาค่าระดับบิต AND ของช่วงที่กำหนด เช่น 7 ลบ
Input: arr[ ] = {1, 3, 1, 2, 32, 3, 3, 4, 4}, q[ ] = {{0, 1}, {3, 5}}
Output:
1
0 0
1 AND 31 = 1
23 AND 34 AND 4 = 00
Input: arr[ ] = {1, 2, 3, 4, 510, 10 , 12, 16, 8}, q[ ] = {{0, 42}, {1, 33, 4}}
Output:
0 8
0 เราจะใช้วิธีเดรัจฉานก่อนและตรวจสอบความซับซ้อนของเวลา หากความซับซ้อนของเวลายังไม่เพียงพอ เราจะพยายามพัฒนาแนวทางที่ดีขึ้น
แนวทางกำลังเดรัจฉาน
ในแนวทางที่กำหนด เราจะสำรวจช่วงที่กำหนดและค้นหาคำตอบของเราและพิมพ์ออกมา
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int main() {
int ARR[] = { 10, 10 , 12, 16, 8 };
int n = sizeof(ARR) / sizeof(int); // size of our array
int queries[][2] = { {0, 2}, {3, 4} }; // 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 = 1LL << 32;
ans -= 1; // making all the bits of ans 1
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;
} ผลลัพธ์
8 0
ในแนวทางนี้ เราเรียกใช้การวนซ้ำตามช่วงของแต่ละการสืบค้นข้อมูลและพิมพ์ส่วนรวมของข้อความค้นหา และดังนั้น ความซับซ้อนโดยรวมของโปรแกรมของเราจึงกลายเป็น 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 == r - l + 1)
ans = ans | 1LL << i;
}
return ans;
}
int main() {
int ARR[] = { 10, 10 , 12, 16, 8 };
int n = sizeof(ARR) / sizeof(int); // size of our array
memset(prefixbits, 0, sizeof(prefixbits)); // initializing all the elements with 0
bitcount(ARR, n);
int queries[][2] = {{0, 2}, {3, 4}}; // 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;
} ผลลัพธ์
2 0
ในแนวทางนี้ เราใช้เวลาคงที่ในการคำนวณข้อความค้นหาที่ลดความซับซ้อนของเวลาลงอย่างมากจาก O(N*Q) ถึง O(N) โดยที่ N คือขนาดของอาร์เรย์ที่เรากำหนดให้ตอนนี้ โปรแกรมนี้สามารถใช้ได้กับข้อจำกัดที่สูงขึ้นเช่นกัน
คำอธิบายของโค้ดด้านบน
ในแนวทางนี้ เรากำลังคำนวณจำนวนบิตนำหน้าทั้งหมดและจัดเก็บไว้ในดัชนี เมื่อเราคำนวณการสืบค้นข้อมูล เราเพียงแค่ต้องตรวจสอบว่าบิตมีจำนวนเท่ากันกับจำนวนองค์ประกอบที่มีอยู่ในช่วงหรือไม่ ถ้าใช่ เราตั้งค่าบิตนี้เป็น 1 ใน x ของเรา และถ้าไม่ใช่ เราจะปล่อยให้บิตนั้นเหมือนกับว่าตัวเลขใดๆ ในช่วงที่กำหนดมีบิต 0 นั้น ดังนั้นค่าบิตทั้งหมด AND ของบิตนั้นจะเป็นศูนย์ และนั่นคือวิธี เรากำลังคำนวณระดับบิตและ
บทสรุป
ในบทความนี้ เราแก้ปัญหาในการแจกแจงแบบสอบถามทั้งหมดสำหรับระดับบิต AND ในช่วงดัชนี [L, R] ของอาร์เรย์ที่กำหนด นอกจากนี้เรายังได้เรียนรู้โปรแกรม C ++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ ( Normal และ มีประสิทธิภาพ ) โดยที่เราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ เราหวังว่าคุณจะพบว่าบทความนี้มีประโยชน์
