c++ - 在给定范围内找到交叉点？

Question

假设数组包含 N (N<=100000) 个元素 a1, a2, .... ,an, 并且给定范围 L, R 其中 1<=L<=R<=N, 你是必需的要获得给定范围内的值的数量，这些值可被集合 S 中的至少一个数字整除，该集合 S 也可以是 {1,2,....,10} 的任何子集。必须使用一种快速的方法，因为它可能会要求您提供多个范围和多个 S(许多查询 Q，Q<=100000)，因此每次循环这些值将非常慢。

我想将可被大集合{1,2,....,10}中的每个数字整除的值的数量存储在10个N个元素的数组中，并进行累加求和以获得可被整除的值的数量O(1) 时间内任何范围内的任何特定数字，例如，如果它需要获得可被以下至少一项整除的值的数量:2、3、5，那么我添加可被它们中的每一个整除的值的数量然后删除交点，但我没有正确地弄清楚如何在每次没有 2^10 或 2^9 计算的情况下计算交点，这也会非常慢(并且可能会消耗大量内存)，因为它可能会完成 100000 次, 有什么想法吗？

Answer 1

你的想法是正确的。您可以使用包含排除原则和前缀和来找到答案。您还需要进行一项观察。

如果集合中有一对数字 a 和 b 使得 a 整除 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 操作来回答每个查询。