C++の整数のストリームで指定された整数の最大XORを見つけます

この問題では、それぞれが次のタイプのいずれかである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データ構造を使用して見つけることができます。各ノードに2つの子ノードがあるトライを使用して、数値の2進値を格納します。この後、タイプ1の各クエリのトライに数値の2進値を追加します。タイプ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