이 문제에서는 각각 다음 유형 중 하나인 Q 쿼리가 제공됩니다.
유형 1 - 데이터 구조에서 값이 i인 요소를 추가하기 위한 삽입(1, i)
유형 2 - findXOR (2, i), 요소 i를 사용하여 데이터 구조의 모든 요소에 대한 XOR을 찾습니다.
데이터 구조는 처음에는 0이 되는 1개의 요소만 포함해야 합니다.
문제를 이해하기 위해 예를 들어보겠습니다.
입력
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 데이터 구조를 사용하여 문제에 대한 솔루션을 찾을 수 있습니다. 각 노드에 두 개의 자식 노드가 있는 트라이를 사용하여 숫자의 이진 값을 저장합니다. 그런 다음 유형 1의 각 쿼리에 대한 트라이에 숫자의 이진 값을 추가합니다. 유형 2의 쿼리에 대해 트라이에서 주어진 값에 대한 경로를 찾은 다음 레벨 카운트가 결과를 제공합니다.
방문에 대한 자세한 내용은 데이터 구조를 참조하십시오.
우리 솔루션의 작동을 설명하는 프로그램
예
#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