より高速なアルゴリズムを開発することが可能です。
Nのビットを呼び出しましょう:a [0]、a [1]、...、a [15]、たとえばN = 13 = 0000000 00001101(バイナリ)の場合、a [0] = a[1]=。 .. a [11] = 0、a [12] = 1、a [13] = 1、a [14] = 0、a [15]=1。
アルゴリズムの主な考え方は次のとおりです。a[0]==1の場合、可能な限り最良の答えはこのビットをゼロにすることです。a [0] == 0の場合、最良の答えはこの位置に1つあります。したがって、最初に、目的のビットを持つ番号があるかどうかを確認します。はいの場合、このビットの数字のみを取得する必要があります。いいえの場合は、逆になります。次に、他のビットを同じ方法で処理します。たとえば、a [0] == 1、a [1] == 0の場合、最初にゼロで始まる数字があるかどうかを確認します。はいの場合、01で始まる数字があるかどうかを確認します。ゼロで始まる数字がない場合は、 11で始まる番号があるかどうかを確認します。
したがって、次のクエリに答えるには、高速なアルゴリズムが必要です。ビットで始まる数値はありますか...範囲の開始、停止にありますか?
1つの可能性:数値の2進表現からトライを構成します。各ノードに、このプレフィックスが配列内にあるすべての位置を格納します(そしてそれらをソートします)。次に、このクエリに答えるのは、このトライを簡単に説明することができます。開始、停止範囲に適切なプレフィックスがあるかどうかを確認するには、ノードに格納されている配列に対してバイナリ検索を実行する必要があります。
これは、より高速な複雑さO(lg ^ 2 N)のアルゴリズムにつながる可能性があります。
これがコードです。あまりテストされていませんが、バグが含まれている可能性があります。
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
class TrieNode {
public:
TrieNode* next[2];
vector<int> positions;
TrieNode() {
next[0] = next[1] = NULL;
}
bool HasNumberInRange(int start, int stop) {
vector<int>::iterator it = lower_bound(
positions.begin(), positions.end(), start);
if (it == positions.end()) return false;
return *it < stop;
}
};
void AddNumberToTrie(int number, int index, TrieNode* base) {
TrieNode* cur = base;
// Go through all binary digits from most significant
for (int i = 14; i >= 0; i--) {
int digit = 0;
if ((number & (1 << i)) != 0) digit = 1;
cur->positions.push_back(index);
if (cur->next[digit] == NULL) {
cur->next[digit] = new TrieNode;
}
cur = cur->next[digit];
}
cur->positions.push_back(index);
}
int FindBestNumber(int a, int start, int stop, TrieNode* base) {
int best_num = 0;
TrieNode* cur = base;
for (int i = 14; i >= 0; i--) {
int digit = 1;
if ((a & (1 << i)) != 0) digit = 0;
if (cur->next[digit] == NULL ||
!cur->next[digit]->HasNumberInRange(start, stop))
digit = 1 - digit;
best_num *= 2;
best_num += digit;
cur = cur->next[digit];
}
return best_num;
}
int main() {
int n; scanf("%d", &n);
int q; scanf("%d", &q);
TrieNode base;
for (int i = 0; i < n; i++) {
int x; scanf("%d", &x);
AddNumberToTrie(x, i, &base);
}
for (int i = 0; i < q; i++) {
int a, start, stop;
// Finds biggest i, such that start <= i < stop and XOR with a is as big as possible
// Base index is 0
scanf("%d %d %d", &a, &start, &stop);
printf("%d\n", FindBestNumber(a, start, stop, &base)^a);
}
}