一道区间问题
题目：给出N个区间，输入一个数字，如果数字本身和数字所有倍数都不在区间，返回true。
区间范围：10e6
用双指针，一个一个的找，不如用哈希。
用哈希，超时了，不知道怎么搞了。
用线段树建这N个区间，这题能用线段树解决吗，我没想到？
12
收起
正在回答
1回答
最好你能把原始问题的题目链接给我，你现在的描述其实并不完全，比如 query 的个数是多少？你给的 10e6 是区间的数量？还是区间右端点的最大值？这些都数据范围都可能决定了最终解决方案的不同。
继续加油！：）
-
目测这个问题需要使用离线查询。先把所有 l, r 合并，列出所有的不合格的位置。之后对于所有的查询，从小到大搜索，每搜索到一个 x，同时把查询中的 2x，3x, 4x 全都判断了，并且在查询中删除。（比如搜索 3 的时候，会判断 99 是否在区间中，那么如果查询中有 99，就不需要重新搜索了，在搜索 3 的时候已经判断过了。）这样做的时间复杂度是 nlogn 的，即调和级数的时间复杂度是 nlogn 的。
无论是离线查询的思路，还是调和级数相关的时间复杂度分析，都完全不是面试范围可能考察的东西。这应该是一道偏竞赛的问题。如果你不是在准备竞赛，这个问题完全可以忽略。
继续加油！：）
2023-02-05 10:07:28
相似问题
mysql插入timestamp时间问题
11
0
4
时区问题 @timestamp 时间录入比本地时间早了8个小时
34
0
12
区间问题
14
0
1
时区设置问题
13
1
3
时区设置问题
22
0
4
登录后可查看更多问答，登录/注册
恭喜解决一个难题，获得1积分~
来为老师/同学的回答评分吧
0 星