ในปัญหานี้ เราได้รับข้อความค้นหาแบบ Q ซึ่งแต่ละคำถามจะเป็นประเภทใดประเภทหนึ่งต่อไปนี้
ประเภทที่ 1 − การแทรก (1, i) เพื่อเพิ่มองค์ประกอบที่มีค่า i ในโครงสร้างข้อมูลของคุณ
ประเภทที่ 2 − findXOR (2, i) เพื่อค้นหา XOR ขององค์ประกอบทั้งหมดของโครงสร้างข้อมูลด้วยองค์ประกอบ i
โครงสร้างข้อมูลควรมีเพียง 1 องค์ประกอบในตอนแรกซึ่งจะเป็น 0
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
Queries: (1, 9), (1, 3), (1, 7), (2, 8), (1, 5), (2, 12)
ผลลัพธ์
15 15
คำอธิบาย
Solving each query,
(1, 9) => data structure => {9}
(1, 3) => data structure => {9, 3}
(1, 7) => data structure => {9, 3, 7}
(2, 8) => maximum XOR(_, 8) = 15, XOR(7, 8)
(1, 5) => data structure => {9, 3, 7, 5}
(2, 12) => maximum XOR(_, 12) = 15, XOR(3, 12) แนวทางการแก้ปัญหา
วิธีแก้ปัญหาสามารถพบได้โดยใช้โครงสร้างข้อมูล trie ซึ่งเป็นแผนผังการค้นหาชนิดพิเศษ เราจะใช้ trie ซึ่งแต่ละโหนดมีโหนดย่อยสองโหนดเพื่อเก็บค่าไบนารีของตัวเลข หลังจากนี้ เราจะเพิ่มค่าไบนารีของตัวเลขลงใน trie สำหรับแต่ละเคียวรีประเภท 1 สำหรับเคียวรีประเภท 2 เราจะค้นหาพาธใน trie สำหรับค่าที่กำหนด จากนั้นการนับระดับจะให้ผลลัพธ์
สำหรับข้อมูลเพิ่มเติมเกี่ยวกับการเยี่ยมชมแบบทดลอง ให้ลองใช้โครงสร้างข้อมูล
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#include<bits/stdc++.h>
using namespace std;
struct Trie {
Trie* children[2];
bool isLeaf;
};
bool check(int N, int i) {
return (bool)(N & (1<<i));
}
Trie* newNode() {
Trie* temp = new Trie;
temp->isLeaf = false;
temp->children[0] = NULL;
temp->children[1] = NULL;
return temp;
}
void insertVal(Trie* root, int x) {
Trie* val = root;
for (int i = 31; i >= 0; i--) {
int f = check(x, i);
if (! val->children[f])
val->children[f] = newNode();
val = val->children[f];
}
val->isLeaf = true;
}
int solveQueryType2(Trie *root, int x){
Trie* val = root;
int ans = 0;
for (int i = 31; i >= 0; i--) {
int f = check(x, i);
if ((val->children[f ^ 1])){
ans = ans + (1 << i);
val = val->children[f ^ 1];
}
else
val = val->children[f];
}
return ans;
}
void solveQueryType1(Trie *root, int x){
insertVal(root, x);
}
int main(){
int Q = 6;
int query[Q][2] = {{1, 9}, {1, 3}, {1, 7}, {2, 8}, {1, 5}, {2, 12}};
Trie* root = newNode();
for(int i = 0; i < Q; i++){
if(query[i][0] == 1 ){
solveQueryType1(root, query[i][1]);
cout<<"Value inserted to the data Structure. value =
"<<query[i][1]<<endl;
}
if(query[i][0] == 2){
cout<<"The maximum XOR with "<<query[i][1]<<" is
"<<solveQueryType2(root, query[i][1])<<endl;
}
}
return 0;
} ผลลัพธ์
Value inserted to the data Structure. value = 9 Value inserted to the data Structure. value = 3 Value inserted to the data Structure. value = 7 The maximum XOR with 8 is 15 Value inserted to the data Structure. value = 5 The maximum XOR with 12 is 15
