xorまたは配列にフィルターを適用した後

Question

元の配列と、各フィルターがフィルターで許可されるインデックスで構成されるフィルターのリストがあります。フィルタはかなりいいです（例：次のように2のべき乗ごとにグループ化されます（フィルタはn = 20まで）。 8 (2^3) = 1 2 3 4 5 6 7 8 17 18 19 20

4 (2^2) = 1 2 3 4 9 10 11 12 17 18 19 20

2 (2^1) = 1 2 5 6 9 10 13 14 17 18

1 (2^0) = 1 3 5 7 9 11 13 15 17 19

は、私はあなたのアイデアを得る願っています。ここでは、元の配列にこれらのフィルタの一部またはすべて（ユーザーが適用するフィルタを指定）を適用し、変換された配列の要素のxorを答えにします。元のアレイが [3 7 8 1 2 9 6 4 11]である場合の例を挙げてください。 n = 9であり、4,2,1のフィルタを適用する必要があった場合、変換は次のようになります。今3及び11、例えばのXORを [3 x x x x x x x 11]

から1のフィルタを適用した後[3 7 x x x x x x 11]

から2のフィルタを適用した後[3 7 8 1 x x x x 11]

から4のフィルタを適用した後

• 8が答えです。私はこのO（n * no。of filter）時間を解決することができますが、O（フィルターなし）時間で答えを出す良い解決策が必要です。 xorのプロパティを利用したり、結果をあらかじめ計算してからフィルタに答えを出す方法はありますか？これは、フィルタを使用するクエリが多いため、O（フィルタなし）時間のクエリに答える必要があるためです。どんな種類の助けにも感謝します。

Answer 1

これは、特定の方法で配列を繰り返し処理することにより、すべてのフィルタを通過させる項目の数であり、すべてのフィルタを渡すインデックスのみを生成するアイテムの数です（O（M）フィルタ。

これは、あなたがゼロから始まる例を書き留めるかどうかを確認するために簡単です：

• 1：0 2 4 6 8 10 12 14 16 18（1を含まない数字）
• 2：0 1 4 5 8 9 12 13 16 17（含まれていない番号2、など）
• 4：0 1 2 3 8 9 10 11 16 17 18 19
• 8：0 1 2 3 4 5 6 7 16 17 18 19

フィルタは実際には配列内のインデックスのビットに対する制約に過ぎません。この制約は、index & filters = 0という形式です。ここで、filtersは、すべての個々のフィルタの合計です（1 + 2 + 4 = 7など）。有効なインデックスiが与えられた場合、次の有効なインデックスi'は、プリミティブ演算のみを用いて計算することができる。i' = (i | filters) + 1 & ~filters。ここでのアイデアは、フィルタリングされたビットをゼロに設定して、+1がそれらを通るようにすることです。次に、フィルタリングされたビットが再びクリアされて、インデックスが有効になります。全体の効果は、フィルタリングされていないビットがインクリメントされ、フィルタリングされたビットがゼロのままであることである。

これは、すべての有効なインデックスに対して直接反復処理を行う簡単なアルゴリズムを提供します。

for (int i = 0; i < N; i = (i | filters) + 1 & ~filters) 
    // do something with array[i], like XOR them all together