与えられた範囲内の交点を見つけるか？

Question

N（N < = 100000）個の要素a1、a2、...、anの配列を仮定し、その範囲にL、Rが与えられている場合、1 < = L < = R < = N指定された集合Sから少なくとも1つの数で割り切れる与えられた範囲内の値の数を得る。この集合は、{1,2、...、10}の任意の部分集合とすることができる。複数の範囲と複数のS（多くのクエリQ、Q < = 100000）を要求する可能性があるため、速い方法を使用する必要があります。そのため、毎回値のループが非常に遅くなります。

大きな集合{1,2、...、10}の各数値で割り切れる値の数をN個の要素の10個の配列にそれぞれ格納し、累積して値の個数を得ることを考えましたO（1）時間内の任意の範囲の任意の数で、例えば、以下のうちの少なくとも1つで割り切れる値の数を取得する必要がある場合：2,3,5、次にそれぞれのそれらの交差点を削除しますが、私は2^10または2^9の計算をせずに交差点を計算する方法を正しく理解していませんでした。毎回、非常に遅くなります。時間、任意のアイデア？

Answer 1

あなたの考えは正しいです。包含関係を除外する原則と接頭辞の合計を使用して答えを見つけることができます。あなたが作る必要があるもう一つの観察があります。

番号aとbのペアがaがbを分割するように設定してありますならば、我々は（確かに、b | x場合、a | x）クエリに対する答えを変更することなく、bを削除することができます。したがって、要素が他の要素を分割しないような集合が常に得られます。

このようなマスクの数は2^10より小さい。事実、それは102です。ここではそれを計算コードは次のとおりです。

def good(mask): 
    for i in filter(lambda b: mask & (1 << (b - 1)), range(1, 11)): 
     if (any(i % j == 0 for j in filter(lambda b: mask & (1 << (b - 1)), range(1, i)))): 
      return False    
    return True 

print(list(filter(good, range(1, 2 ** 10))))) 

したがって、我々は前処理が店に約100N操作と番号が必要です（それが合理的に小さな見えます）。

また、「良い」マスクにはほとんどの5要素があります（上記のコードを使用して確認できます）。したがって、約2^5の操作を使用して各クエリに答えることができます。