找到給定範圍內的交叉點？

假設N（N < = 100000）個元素爲a1，a2，...，an的數組，並給出您在其中的範圍L，R其中1 < = L < = R < = N，您需要獲得給定範圍內的值的數量，該值可以由給定的集合S中的至少一個數字整除，該集合可以是{1,2，...，10}的任何子集。必須使用快速方式，因爲它可能會要求您提供多個範圍和多個S（許多查詢Q，Q < = 100000），因此每次循環值都會非常緩慢。找到給定範圍內的交叉點？

我想在每個N元素的10個數組的10個數組中存儲可由每個數字整除的大數集{1,2，...，10}的值的數量，並且做累計和以獲得可除數的值的數量在O（1）時間內的任何範圍內的任何特定數字，例如，如果它需要得到可被下列至少一項整除的值的數目：2,3,5，那麼我加上可被每一個整除的值的數目他們然後刪除交叉點，但我沒有正確計算出如何計算每次沒有2^10或2^9計算的交點，這也將非常緩慢（並且可能非常耗費內存），因爲它可能會完成100000次時間，任何想法？

來源

2017-01-21 Mohamed EL Tair

這看起來像是來自編程競賽，你可以給源代碼鏈接嗎？ –

這是一個seg-tree問題。你可以檢查[這些]（http://stackoverflow.com/questions/tagged/segment-tree），或閱讀關於結構和算法[這裏]（http://codeforces.com/blog/entry/15890） –

你的想法是正確的。您可以使用包含 - 排除原則和前綴總和來找到答案。你只需要再做一次觀察。

如果有一對數字的集合，使得a分ba和b的，我們可以刪除b不改變答案的查詢（事實上，如果b | x，然後a | x）。因此，我們總是得到一個集合，使得任何元素都不會分裂任何其他元素。

該掩碼的數量小於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操作來回答每個查詢。

來源

2017-01-21 08:39:03 kraskevich

找到給定範圍內的交叉點？

回答

相關問題