Блог пользователя stould

Автор stould, история, 9 лет назад, По-английски

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 ?

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

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

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    disconsider.

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.