Hello community. I'll show the following statement:
Given N segments [Li, Ri] and Q queries Xi. Each query will ask if the Xi is inside some segment.
0 ≤ Li, Ri ≤ 109
Will at most 105 segments and at most 105 queries.
I have solved this problem sorting the segments, sorting the queries, and finally T(N+Q) processing. I am thinking now, if is it possible to be solved faster?.. But nothing comes to me.
Do you know something faster ?
Can you go more in depth into your O(N + Q) processing? The solutions I'm thinking of take either O(NQ) or O(Q logN) processing time.
I guess, only the last stage is O(N + Q); the first stage is sorting and so the total complexity in this solution is O(NlogN + QlogQ).
N+Q is what you need to get inputs...
I'm sorry, I made a mistake, I'll fix and give more details.
I'll be more precise on the algorithm:
First, sort all N segments in N*log(N), sort all queries in Q*log(Q), and after all, process in O(N+Q) in the following way:
Starting from the first point Q[0] and the first segment, I'll move to the next point until Q[i] lies on the segment. Pass to the next segment and repeat the process.
Well i guess this can be done in O(N * log(log(N)) + N + Q) using Van Emde Boas tree, but this aproach will require like 10^9 in memory. I am not sure btw
I fixed, N ≤ 105.
No, i meant 10^9 memory
I think it can be done online in O(N*log(N) + Q*log(N)) using treaps (or any other BBST), where each node will represent an interval. In each node, you keep three informations:
So, for each query Xi you do a DFS at the treap and, for each node:
Xi >= node->a and Xi <= node->b, return true;Xi <= node->L->max_b, go to the left child;Seems like u misunderstood op's question(he wants faster). Ur approach is 0(Log(N) * (Q + N)) anyway
Yes, It's not faster. I just provide a way to solve the problem in the same complexity without the need of pre-processing the segments.
In this way the complexity will be the same even if the segments were possibly given between the queries.
disconsider.
If it is OK to use hashmap and solve offline:
Let's store vector of opening and closing of queries in each index of an array. Then move from left to right and maintain hashmap (number) -> (number of arrearances on prefix). For each opening of query we will subtract the number of appearances on prefix, for each closing — add.
It is O(n+q) on average.