c++ - 奇数组中包含的数字

Question

我有一个家庭作业问题，我只能在 O(max(F)*N) 中解决(N 大约是 10^5 和 F 是 10^9) 复杂度，我希望你能帮助我。我得到了 N 组 4 个 integer 数字(名为 S、F、a 和 b)；每组 4 个数字以这种方式描述一组数字:第一个连续的数字，从 S 开始包括在集合中。下一个 b 连续数字不是，然后下一个 a 数字是，重复此操作直到达到上限 F。例如对于 S=5;F=50;a=1;b=19 集合包含 (5,25,45); S=1;F=10;a=2;b=1 该集合包含 (1,2,4,5,7,8,10);

我需要找到包含在奇数组中的整数。保证对于给定的测试只有 1 个数字符合此条件。

我试图遍历 min(S) 和 max(F) 之间的每个数字，并检查这个数字包含多少组，如果它包含在奇数个集合中，那么这就是答案。正如我所说，通过这种方式，我得到了太多的 O (F*N)，而且我不知道如何查看一个数字是否在奇数组中。

如果你能帮助我，我将不胜感激。提前谢谢你，抱歉我的英语和解释不好!

Answer 1

提示

我很想使用二分法。

选择一个值 x，然后计算所有集合中有多少个数字<=x。

如果这是奇数，那么答案是 <=x，否则 >x。

这需要时间 O(Nlog(F))

替代解释

假设我们有集合

[S=1,F=8,a=2,b=1]->(1,2,4,5,7,8) 
[S=1,F=7,a=1,b=0]->(1,2,3,4,5,6,7) 
[S=6,F=8,a=1,b=1]->(6,8)

然后我们可以表:

N(y) = y 被包含在一个集合中的次数，

C(z) = sum(N(y) for y in range(1,z)) % 2

y  N(y)  C(z)
1  2     0
2  2     0
3  1     1
4  2     1
5  2     1
6  2     1
7  2     1
8  2     1

然后我们使用二分法找到第一个 C(z) 变为 1 的地方。