stould's blog

Working on 1-d coordinate.
By stould, history, 9 years ago, In English

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 ?

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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).

    → Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

N+Q is what you need to get inputs...

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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:

  • a = the left index of this segment (it will be the key of the treap);
  • b = the right index of this segment;
  • max_b = the maximal value of b in the subtree rooted at this node.

So, for each query Xi you do a DFS at the treap and, for each node:

  • If the current node is null, return false;
  • If Xi >= node->a and Xi <= node->b, return true;
  • If Xi <= node->L->max_b, go to the left child;
  • Otherwise, go to the right child.
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Seems like u misunderstood op's question(he wants faster). Ur approach is 0(Log(N) * (Q + N)) anyway

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    disconsider.

    → Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

→ Reply